LeetCode 题解（99）: Largest Rectangle in Histogram

本文主要是介绍LeetCode 题解（99）: Largest Rectangle in Histogram，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

题解：

网上学来神算法。用堆栈保存height的index。

C++版：

class Solution:# @param {integer[]} height# @return {integer}def largestRectangleArea(self, height):height.append(0)maxArea = 0i = 0index = []while i < len(height):if len(index) == 0 or height[index[-1]] <= height[i]:index.append(i)i += 1else:t = index.pop()if len(index) == 0:maxArea = max(maxArea, height[t] * i)else:maxArea = max(maxArea, height[t] * (i - 1 - index[-1]))return maxArea

Java版：

public class Solution {public int largestRectangleArea(int[] height) {int[] h = new int[height.length + 1];h = Arrays.copyOf(height, height.length + 1);Stack<Integer> index = new Stack<>();int i = 0;int maxArea = 0;while(i < h.length) {if(index.isEmpty() || h[index.peek()] <= h[i]) {index.push(i++);} else {int t = index.pop();maxArea = Math.max(maxArea, h[t] * (index.isEmpty() ? i : i - 1 - index.peek()));}}return maxArea;}
}

Python版：

class Solution:# @param {integer[]} height# @return {integer}def largestRectangleArea(self, height):height.append(0)maxArea = 0i = 0index = []while i < len(height):if len(index) == 0 or height[index[-1]] <= height[i]:index.append(i)i += 1else:t = index.pop()if len(index) == 0:maxArea = max(maxArea, height[t] * i)else:maxArea = max(maxArea, height[t] * (i - 1 - index[-1]))return maxArea

这篇关于LeetCode 题解（99）: Largest Rectangle in Histogram的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---