赞
踩
题目:84. 柱状图中最大的矩形
解析:代码随想录解析
反方向接雨水。见上一篇文章
class Solution { public int largestRectangleArea(int[] heights) { int[] newHeights = new int[heights.length+2]; System.arraycopy(heights, 0, newHeights, 1, heights.length); int res = 0; Stack<Integer> stack = new Stack<>(); stack.push(0); for (int i = 1; i < newHeights.length; i++) { if (newHeights[i] > newHeights[stack.peek()]) stack.push(i); else if (newHeights[i] == newHeights[stack.peek()]) { stack.pop(); stack.push(i); } else { while (newHeights[i] < newHeights[stack.peek()]) { int mid = stack.peek(); stack.pop(); int left = stack.peek(); int h = newHeights[mid]; int w = i - left - 1; res = Math.max(res, w * h); } stack.push(i); } } return res; } } //双指针 class Solution { public int largestRectangleArea(int[] heights) { int length = heights.length; int []leftHeight = new int[length]; int []rightHeight = new int[length]; leftHeight[0] = -1; for (int i = 1; i < length; i++) { int t = i-1; while (t >= 0 && heights[t] >= heights[i]) t = leftHeight[t]; leftHeight[i] = t; } rightHeight[length-1] = length; for (int i = length-2; i >= 0; i--) { int t = i+1; while (t < length && heights[t] >= heights[i]) t = rightHeight[t]; rightHeight[i] = t; } int res = 0; for (int i = 0; i < length; i++) { int area = (rightHeight[i] - leftHeight[i] - 1) * heights[i]; res = Math.max(res, area); } return res; } }
暂无
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。