代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形

简介: 代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形

代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形

1. LeetCode 84. 柱状图中最大的矩形

1.1 思路

  1. 本题是给一个数组形象得画出图后求矩形的最大面积是多少。本题和42. 接雨水是有点呼应的,接雨水是求外面形成最大的接水面积,本题是求柱子的内部最大面积。
  2. 以 [2,1,5,6,2,3] 以 1 高度为基准的柱子,左边找比其矮没找到,右边找比其矮也没找到,那这个 1 的高度就可以贯穿整个数组,因此底为数组长度 6,面积则为 6*1 等于 6。那再以 5 为基准,左边找到第一个比其矮的 1,因此无法向左扩展,右边找到第一个比其矮的 2,因此只能向右扩展到 6,因此高为 5,宽为 2,面积为 10。即以每个柱子为基准,向左右找第一个比其矮的柱子,然后就可以确定他们的宽,高就是这个柱子的高度,每个柱子都算一次,最后得到最大的即可。
  3. 单调栈:本题就是求左边和右边第一个比当前元素小的。因此单调栈从栈顶到栈底应该是递减的。本题和42. 接雨水也是一样,都是确定三个元素,当前的基准柱子、左边第一个比当前小的、右边第一个比当前小的。当当前元素比栈顶小的时候就是收获结果的时候,栈顶元素就是 middle,左边第一个小的元素 left 就是栈顶下一个元素,右边第一个小的元素 right 就是当前元素。高 h 就是 heights[middle],宽 w=right-left-1,面积就是 h*w。
  4. 数组首尾加 0:在本题的数组的头尾各加一个 0,为什么?因为本题用的是单调递减栈,首先要是数组出现 [2,4,6,8] 这种情况,那放入栈的时候就是 8,6,4,2 这样的顺序,右边是栈底,左边是栈顶,那这样的话一直都没有走到计算结果的步骤,因为一直都没有遍历到当前元素比栈顶元素小的情况,那就无法计算结果,因此末尾要加 0,这样才能触发计算结果的过程。然后要是数组出现 [8,6,4,2] 这种情况,那放入栈的时候先是 8 然后当前元素是 6,此时就触发计算结果的过程了,但是我们计算结果需要 3 个元素,这里少了个左边第一个小的元素 left,而我们代码中为了避免对空栈操作,这一步骤就跳过了,然后 8 出栈,6 入栈,后面依然是这种情况,又无法计算结果,因此头部要加 0。
  5. 代码实现:定义 result 记录最大的结果。定义栈,然后在数组收尾各自插入 0,然后将 0 下标入栈。for(int i=1;i<heights.length;i++)从 1 开始是因为 0 下标已经存入。当前元素大于等于栈顶元素时就直接 stack.push(i),等于的情况直接入栈,或者将栈顶弹出再入栈都行,只是多了个结果为 0 的操作步骤。如果小于就 while(!stack.empty()&&heights[i]<heights[stack.peek())先选取基准柱子,middle=stack.pop(),为什么直接弹出而不是 peek,因为我们要求 left,这个在栈顶下一个元素。然后接着 if(!stack.empty())left=stack.peek(),right=i,高 h=heights[middle],宽 w=right-left-1。result=Math.max(result,h*w)。然后 while 循环结束就要 stack.push(i)。最终 return result 就行。

1.2 代码

class Solution {
    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();
        
        // 数组扩容,在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;
        
        st.push(0);
        int result = 0;
        // 第一个元素已经入栈,从下标1开始
        for (int i = 1; i < heights.length; i++) {
            // 注意heights[i] 是和heights[st.top()] 比较 ,st.top()是下标
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
                st.pop(); // 这个可以加,可以不加,效果一样,思路不同
                st.push(i);
            } else {
                while (heights[i] < heights[st.peek()]) { // 注意是while
                    int mid = st.peek();
                    st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                st.push(i);
            }
        }
        return result;
    }
}


相关文章
|
4天前
|
算法
【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
|
4天前
|
算法
【优选算法】——Leetcode——611. 有效三角形的个数
【优选算法】——Leetcode——611. 有效三角形的个数
|
4天前
|
算法 容器
【优选算法】—Leetcode—11—— 盛最多水的容器
【优选算法】—Leetcode—11—— 盛最多水的容器
|
4天前
|
算法
【优选算法】——Leetcode——202—— 快乐数
【优选算法】——Leetcode——202—— 快乐数
【优选算法】——Leetcode——202—— 快乐数
|
4天前
|
算法
[优选算法]——双指针——Leetcode——1089. 复写零
[优选算法]——双指针——Leetcode——1089. 复写零
|
3天前
|
算法 索引
力扣刷题【第一期】
这是一个关于算法的总结,包含7个不同的问题。1)爬楼梯问题,使用动态规划,通过迭代找到到达n阶楼梯的不同方法数。2)两数之和,通过双重循环找出数组中和为目标值的两个数的索引。3)移动零,使用双指针将数组中的0移到末尾。4)合并有序链表,创建新链表按升序合并两个链表。5)删除链表重复值,遍历链表删除重复元素。6)环形链表检测,使用快慢指针判断链表是否有环。7)相交链表,计算链表长度找
8 1
|
3天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
10 0
|
12天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
12 0
|
12天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
16 0