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

2020-04-05 16:02:08来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

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

题目

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

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

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为?[2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积,其面积为?10?个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路1-直接双层遍历,暴力解题

步骤:

  1. 外层循环每次选定i作为中心;
  2. 内层循环每次以i作为中心向两侧扩展,扩展的高不能低于i;
  3. 计算可扩展的最大面积,计算所有i扩展面积中的最大值;

效率:

  • 时间复杂度:O(n2)
  • 空间复杂度O(1)

思路2-使用单调栈

步骤:

  1. 新建栈,从左向右遍历入栈,入栈的条件是,当前即将入栈的柱子高度必须不低于当前栈顶的柱子高度,即柱子是单调递增的;
  2. 若当前柱子低于栈顶的柱子高度,说明之前的柱子高度不能再扩展了,需要从栈顶依次弹出并计算以每个栈元素为高时的矩形面积,直到栈顶柱子高度不高于当前柱子高度;
  3. 在2中计算到当前栈顶柱子高度不高于当前即将入栈的柱子高度时,当前柱子入栈;
    • 上面的步骤有一个缺陷:若所有的柱子都是递增的,则矩形的面积就不曾计算过,所以还需要再加一个第4步;
  4. 在1新建栈时就压入一个垫底的数-1,在完成123步骤后,再以2的逻辑处理栈中的所有元素直到栈中只剩-1;
    图解:

总结:单调栈也是算法中一个很有用的特性,需要多熟悉学习应用

算法源码示例

package leetcode;

import java.util.Stack;

/**
 * @author ZhouJie
 * @date 2020年4月4日 下午12:51:29 
 * @Description: 84. 柱状图中最大的矩形
 *
 */
public class LeetCode_0084 {

}

class Solution_0084 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年4月4日 下午1:17:32 
	 * @param: @param heights
	 * @param: @return
	 * @return: int
	 * @Description: 1-一次遍历,遍历中左右扩展,实际算法复杂度为O(n2)
	 *
	 */
	public int largestRectangleArea_1(int[] heights) {
		int len = 0;
		if (heights == null || (len = heights.length) == 0) {
			return 0;
		}
		int maxArea = 0;
		for (int i = 0; i < len; i++) {
			if (heights[i] != 0) {
				int l = i, r = i, h = heights[i];
				while (l > 0 && heights[l - 1] >= h) {
					l--;
				}
				while (r < len - 1 && heights[r + 1] >= h) {
					r++;
				}
				maxArea = Math.max(maxArea, h * (r - l + 1));
			}
		}
		return maxArea;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月4日 下午1:43:01 
	 * @param: @param heights
	 * @param: @return
	 * @return: int
	 * @Description: 2-单调栈
	 *
	 */
	public int largestRectangleArea_2(int[] heights) {
		int len = 0;
		if (heights == null || (len = heights.length) == 0) {
			return 0;
		}
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(-1);
		int maxArea = 0;
		for (int i = 0; i < len; i++) {
			while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
				maxArea = Math.max(maxArea, heights[stack.pop()] * (i - stack.peek() - 1));
			}
			stack.push(i);
		}
		while (stack.peek() != -1) {
			maxArea = Math.max(maxArea, heights[stack.pop()] * (len - stack.peek() - 1));
		}
		return maxArea;
	}

}


原文链接:https://www.cnblogs.com/izhoujie/p/12636834.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:java 列表迭代器

下一篇:【Springboot】实例讲解Springboot整合OpenTracing分布式链路追