42. 接雨水

接雨水這道題目是 面試中特別高頻的一道題，也是單調棧 應用的題目，大家好好做做。

建議是掌握 雙指針 和單調棧，因為在面試中 寫出單調棧可能 有點難度，但雙指針思路更直接一些。

在時間緊張的情況有，能寫出雙指針法也是不錯的，然后可以和面試官在慢慢討論如何優化。

代碼隨想錄

class Solution {
public:int trap(vector<int>& height) {stack<int>st;int res=0;for (int i=0;i<height.size();i++){if (st.empty() || height[st.top()]>height[i])st.push(i);else{while(!st.empty() && height[st.top()]<height[i]){int mid=st.top();st.pop();if (!st.empty())res+=(i-st.top()-1)*(min(height[st.top()],height[i])-height[mid]);}st.push(i);}}return res;}
};

總結

把左邊最大和右邊最大就是要求面積的思路理清楚了其實后面實現就不難了。

84.? 柱狀圖中最大的矩形

有了之前單調棧的鋪墊，這道題目就不難了。

ongjiez代碼隨想錄

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int>st;heights.insert(heights.begin(), 0); // 數組頭部加入元素0heights.push_back(0); // 數組尾部加入元素0st.push(0);int res=0;for (int i=1;i<heights.size();i++){if (st.empty() || heights[st.top()]<heights[i])st.push(i);else{while (!st.empty() && heights[st.top()]>heights[i]){int mid=st.top();st.pop();if (!st.empty())res=max(res,heights[mid]*(i-st.top()-1));else res=max(res,heights[mid]*i);}st.push(i);}}return res;}
};

總結

我還在想怎么把棧剩余的元素給算上，原來在后面加上個0就可以了。