• 算法刷题记录 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
  • 相关阅读:
    C++智能指针shared_ptr用法
    macOS鼠标管理操作增强BetterMouse简体中文
    设计模式:适配器模式
    【产品】家用工商业储能计量表ADL3000-E-B系列导轨式多功能电能表 UL认证 /CE认证 /485通讯
    通信接口五种主要的类型是什么?RS-232、485、CAN、USB
    安装robotframework的RIDE/wxPython 依赖VC的编译器, 使用VC BuildTool 解决
    【图像隐写】基于matlab遗传算法的奇异值分解数字水印嵌入提取【含Matlab源码 2115期】
    云计算及其应用知识点总结
    ip大小比较的方法
    文章参考链接
  • 原文地址:https://blog.csdn.net/qq_45542288/article/details/138064168