參考

思路1: 暴力解法

• 找每個柱子的左右高度
• 超時 O(N^2)
  

思路2: 雙指針優化

class Solution {
public:int trap(vector<int>& height) {vector<int> lheight(height.size(), 0);vector<int> rheight(height.size(), 0);lheight[0] = height[0];for (int i = 1; i < height.size(); i++) {lheight[i] = max(lheight[i - 1], height[i]);}rheight[height.size() - 1] = height[height.size() - 1];for (int i = height.size() - 2; i >= 0; i--) {rheight[i] = max(rheight[i + 1], height[i]);}int res = 0;for (int i = 0; i < height.size(); i++) {if (i == 0 || i == height.size() - 1) continue;int min_val = min(lheight[i], rheight[i]);if (min_val - height[i] > 0) res += min_val - height[i];}return res;}
};

思路3: 單調棧

class Solution {
public:int trap(vector<int>& height) {int res = 0;stack<int> mystack;mystack.push(0);for (int i = 1; i < height.size(); i++) {if (height[i] < height[mystack.top()]) {mystack.push(i);} else if (height[i] == height[mystack.top()]) {mystack.push(i);} else {while (!mystack.empty() && height[i] >= height[mystack.top()]) {int right = i;int mid = mystack.top();mystack.pop();if (mystack.empty()) break;//元素數量不滿足時, 無需回退上一步的pop操作, 放心舍棄元素(構不成封閉區間)int left = mystack.top();int w = right - left - 1;res += (min(height[left], height[right]) - height[mid]) * w;}mystack.push(i);}}return res;}
};

//對比: 細節處理存在問題, 雖然能通過, 實際上并不是單調棧(首元素的影響)
while (mystack.size() > 1 && height[i] >= height[mystack.top()]) {int right = i;int mid = mystack.top();mystack.pop();int left = mystack.top();int w = right - left - 1;if (min(height[left], height[right]) - height[mid] > 0)res += (min(height[left], height[right]) - height[mid]) * w;
}

思路: 單調棧
和接雨水相似, 區別在棧內元素輕的沉底
首插入0避免出現棧內元素不滿足2的情況(如 3 1 2)
尾插入0避免出現一直滿足棧條件而無法收獲結果的情況(如 2 3 4 5)

class Solution {
public:int largestRectangleArea(vector<int>& heights) {heights.insert(heights.begin(), 0);heights.push_back(0);stack<int> mystask;mystask.push(0);int res = 0;for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[mystask.top()]) {mystask.push(i);} else if (heights[i] == heights[mystask.top()]) {mystask.push(i);} else {while (!mystask.empty() &&heights[i] < heights[mystask.top()]) {int right = i;int mid = mystask.top();mystask.pop();if (!mystask.empty()) {int left = mystask.top();int tem = (right - left - 1) * heights[mid];res = max(res, tem);}}mystask.push(i);}}return res;}
};

思路: 雙指針
實現方式不同, 此處存放的是下標索引

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int res = 0;vector<int> L_index(heights.size());vector<int> R_index(heights.size());for (int i = 0; i < heights.size(); i++) {int t = i;while (t > 0 && heights[t - 1] >= heights[i]) t = L_index[t - 1];//若改為 t--則會超時L_index[i] = t;}for (int i = heights.size() - 1; i >= 0; i--) {int t = i;while (t + 1 < heights.size() && heights[i] <= heights[t + 1]) t = R_index[t + 1];R_index[i] = t;}for (int i = 0; i < heights.size(); i++) {int W = R_index[i] - L_index[i] + 1;int tem = W * heights[i];res = max(res, tem);}return res;}
};