11.6 leetcode打卡（单调栈）

11.6 leetcode打卡

42.接雨水

原题链接：42. 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
1
2

代码实现

class Solution {
public:
    int trap(vector& height) {
        int n = height.size(), ans = 0;
        stack stack;
        for(int i = 0; i < n; ++ i){
            while(!stack.empty() && height[stack.top()] < height[i]){
                int cur = stack.top();
                stack.pop();
                if(stack.empty())  break;
                int l = stack.top();    //左边柱子
                int r = i;              //右边柱子
                int h = min(height[l], height[r]) - height[cur];
                ans += (r - l - 1) * h;
            }
            stack.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

84.柱状图中的最大矩形

原题链接：84. 柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

输入：heights = [2,1,5,6,2,3]
输出：10
1
2

解题思路

单调栈

1. 对于一个高度，如果能得到向左和向右的边界
2. 那么就能对每个高度求一次面积
3. 遍历所有高度，即可得出最大面积
4. 使用单调栈，在出栈操作时得到前后边界并计算面积

处理边界

为了应对数组数组中只有一个或者两个元素的情况，可以现在数组的头和尾分别插入一个元素0，以保证计算时的边界问题

如[2, 4] 元素都入栈了，并没有进入计算面积的代码块。

代码实现

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        stack stack;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int ans = 0, n = heights.size();
        for(int i = 0; i < n; ++ i){
            while(!stack.empty() && heights[stack.top()] > heights[i]){
                int cur = stack.top();         //记录当前的高度
                stack.pop();
                int l = stack.top();           //记录左边界， 即左边第一个比当前小的
                int r = i;                     //记录右边界
                ans = max((r - l - 1) * heights[cur], ans);
            }
            stack.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

739.每日温度

原题链接：739. 每日温度

题目描述

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
1
2

解题思路

常规思路

代码实现

class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
        int len = temperatures.size();
        vector res;
        stack stack;
        for(int i = len - 1; i >= 0; -- i){
            while(!stack.empty() && temperatures[i] >= temperatures[stack.top()]) stack.pop();
            int tmp = stack.empty() ? 0 : stack.top() - i;
            res.push_back(tmp);
            stack.push(i);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16