Givennnon-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 =10unit.
For example,Given height =[2,1,5,6,2,3],
return10.
题意:求直方图中最大面积的矩形。
思路:单调栈的应用。维持一个单调递增的栈,,网上写的可以转来:题解
public class Solution {public int largestRectangleArea(int[] height) {Stack<Integer> stack = new Stack<Integer>();int i = 0;int ans = 0;int h[] = new int[height.length+1];h = Arrays.copyOf(height, height.length+1);while (i < h.length) {if (stack.isEmpty() || h[stack.peek()] <= h[i])stack.push(i++);else {int t = stack.pop();ans = Math.max(ans, h[t] * (stack.isEmpty() ? i : i – stack.peek() – 1));}}return ans;}}
勤奋,它是一块可以吸引到一切美好事物的天然磁石,它比黄金珍贵,