文章目录
- 今日记录
- 42. 接雨水
- 84.柱状图中最大的矩形
- 总结
今日记录
42. 接雨水
Leetcode链接
class Solution {
public:int trap(vector<int>& height) {stack<int> st;st.push(0);int sum = 0;for (int i = 1; i < height.size(); i++) {if (height[i] < height[st.top()]) {st.push(i);} else if (height[i] == height[st.top()]) {st.pop();st.push(i);} else {while (!st.empty() && height[i] > height[st.top()]) {int mid = st.top();st.pop();if (!st.empty()) {int h = min(height[st.top()], height[i]) - height[mid];int w = i - st.top() - 1;sum += h * w;}}st.push(i);}}return sum;}
};
84.柱状图中最大的矩形
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;st.push(0);heights.insert(heights.begin(), 0);heights.push_back(0);for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) {st.push(i);} else if (heights[i] == heights[st.top()]) {st.pop();st.push(i);} else {while (!st.empty() && heights[i] < heights[st.top()]) {int mid = st.top();st.pop();int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}return result;}
};
