算法刷题记录 Day52

算法刷题记录 Day52

Date: 2024.04.20

lc 84. 柱状图中最大的矩形

// 单调栈
class Solution {
public:
    int largestRectangleArea(vector& heights) {
        // 对于每个柱子，我们考虑按当前柱子进行中心扩散，直到找到其左侧及其右侧，高度小于该柱子的柱子为止。
        // 例如当前柱子高度为2，则所有高度大于等于2的柱子都可以加入该柱子为高的矩形。
        // 因此，我们需要找到左侧和右侧第一个高度小于指定高度的柱子。（则范围内均为大于等于该高度的柱子）
        int n = heights.size();
        vector leftIdx(n, 0);
        vector rightIdx(n, 0);

        // 我们借助单调栈获取左右第一个高度小于指定高度的数。
        // 要获取左侧最近较小值，我们维护一个单调递增的栈。每当一个元素要入栈，我们舍去栈顶的大于该元素的值。
        // 若栈不为空，则此时的栈顶，即为该元素的左侧第一个更小值。若栈为空，则左侧第一个更小值视作0.
        stack st;
        for(int i=0; i heights[st.top()]){
                leftIdx[i] = st.top();
            }
            else if(!st.empty() && cur_height <= heights[st.top()]){
                while(!st.empty() && cur_height <= heights[st.top()]){
                    st.pop();
                }
                if(st.empty()){
                    leftIdx[i] = -1;
                }
                else{
                    leftIdx[i] = st.top();
                }
            }
            else if(st.empty()){
                leftIdx[i] = -1;
            }
            st.push(i);
        }

        while(!st.empty()){
            st.pop();
        }

        for(int i=n-1; i>=0; i--){
            int cur_height = heights[i];
            if(!st.empty() && cur_height > heights[st.top()]){
                rightIdx[i] = st.top();
            }
            else if(!st.empty() && cur_height <= heights[st.top()]){
                while(!st.empty() && cur_height <= heights[st.top()]){
                    st.pop();
                }
                if(st.empty()){
                    rightIdx[i] = n;
                }
                else{
                    rightIdx[i] = st.top();
                }
            }
            else if(st.empty()){
                rightIdx[i] = n;
            }
            st.push(i);
        }

        int max_area = -1;
        for(int i=0; i& heights) {
        int max_area = INT_MIN;
        int n = heights.size();
        // 遍历起点和终点，矩形高为所有点中min，宽为（终点-起点+1）;
        for(int start = 0; start < n; start++){
            int cur_min = heights[start];
            for(int end = start; end < n; end++){
                cur_min = min(cur_min, heights[end]);
                int cur_area = (end - start + 1) * cur_min;
                max_area = max(max_area, cur_area);
            }
        }
        return max_area;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91