LeetCode 84. Largest rectangle in histogram

My LeetCode: https://leetcode-cn.com/u/ituring/

My LeetCode source code [GitHub]: https://github.com/izhoujie/Algorithmcii

LeetCode 84. Largest rectangle in histogram

subject

n nonnegative integers are given to represent the height of each column in the histogram. Each column is adjacent to each other and has a width of 1.

Find the maximum area of the rectangle that can be outlined in the histogram.

The above is an example of a histogram where the width of each column is 1 and the given height is [2,1,5,6,2,3].

The shaded part in the figure is the largest rectangular area that can be outlined, with an area of 10 units.

Example:

Input: [2,1,5,6,2,3]
Output: 10

Source: LeetCode
Links: https://leetcode-cn.com/problems/largest-rectangle-in-histogram
Copyright belongs to the network. For commercial reprint, please contact the official authorization. For non-commercial reprint, please indicate the source.

Solving problems

Train of thought 1 - direct double level ergodic, violent problem solving

Steps:

  1. i was selected as the center of the outer cycle;
  2. Each time, the inner circle expands to both sides with i as the center, and the expanding height cannot be lower than i;
  3. Calculate the maximum extensible area and the maximum of all i extended areas;

Efficiency:

  • Time complexity: O(n ²)
  • Spatial complexity O(1)

Idea 2 - use monotone stack

Steps:

  1. When a new stack is built, the stack is traversed from left to right. The condition for the stack is that the height of the column to be stacked must not be lower than the height of the column on the top of the current stack, that is, the column is monotonically increasing;
  2. If the current column height is lower than the column height on the top of the stack, it means that the previous column height can no longer be expanded. It needs to pop up from the top of the stack and calculate the rectangular area when each stack element is high, until the column height on the top of the stack is not higher than the current column height;
  3. In 2, when the height of the column at the top of the current stack is not higher than the height of the column to be stacked, the current column will be stacked;
    • There is a flaw in the above step: if all columns are incremental, the area of the rectangle has not been calculated, so another step 4 needs to be added;
  4. When a new stack is created in 1, a bottom number - 1 is pressed. After 123 steps are completed, all elements in the stack are processed in 2 logic until only - 1 is left in the stack;
    Illustration:

Summary: monotone stack is also a very useful feature of algorithm, which requires more familiarity with learning applications

Algorithm source code example

package leetcode;

import java.util.Stack;

/**
 * @author ZhouJie
 * @date 2020 12:51:29 PM, April 4, 2004 
 * @Description: 84. The largest rectangle in a histogram
 *
 */
public class LeetCode_0084 {

}

class Solution_0084 {
	/**
	 * @author: ZhouJie
	 * @date: 2020 1:17:32 PM, April 4, 2004 
	 * @param: @param heights
	 * @param: @return
	 * @return: int
	 * @Description: 1-Once traversing, extending left and right in traversing, the actual algorithm complexity is O(n ²)
	 *
	 */
	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 April 4, 2001 1:43:01 PM 
	 * @param: @param heights
	 * @param: @return
	 * @return: int
	 * @Description: 2-Monotonic stack
	 *
	 */
	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;
	}

}

Tags: Java github network

Posted on Sun, 05 Apr 2020 15:39:18 -0700 by trrobnett