这两题看起来有点像,但是实际上是完全不一样的,区别在于:
The "Container With Most Water" solution will allow the water to rise above intermediate positions. With the "largest rectangle" problem, the rectangle cannot rise above intermediate bars.
也就是说Container With Most Water只考虑左右边界,[i,j]范围内的Area = min(height[i],height[j]) * (j-i);而Largest Rectangle in Histogram,高度最小值为[i,j]范围内所有高度的最小值。后者比前者要难很多
1.Container With Most Water
对于这题,考虑左右边界[i,j] ,当height[i]<height[j]时,因为i是其中的短板,则无论j取[i+1,j]中的任何值,Area都只会比当前已求出的[i,j]的Area小(横坐标范围减小,再遇见比height[i]更小的右边界),因此以i为左边界的情况不再考虑,i++;反之,j--,同样的思考方式。
代码:
public class Solution { public int min(int i,int j){ return i<j?i:j; } public int maxArea(int[] height) { // Note: The Solution object is instantiated only once and is reused by each test case. if(height == null) return 0; int i = 0; int j = height.length -1; int max = 0; while(i<j){ int area = min(height[i],height[j])*(j-i); if(area>max) max = area; if(height[i]<height[j]) i++; else j--; } return max; } }
Largest Rectangle in Histogram
代码如下:
public int largestRectangleArea(int[] height) { // Note: The Solution object is instantiated only once and is reused by each test case. if(height == null) return 0; int len = height.length; Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> width = new Stack<Integer>();//记录向左可以扩展的宽度 int max = 0; stack.push(0); width.push(0); int h; for(int i = 0;i<=len;i++){ if(i == len) h = 0; else h = height[i]; int wid = 0; while(h<stack.peek()){ //1.算自己的左边界 //2.已放入栈中的高度>h的右边界已经找到了 int top = stack.pop(); wid += width.pop(); max = Math.max(max,top*wid); } stack.push(h); width.push(Math.max(wid+1,1));//每次加入stack的时候,他的左边界就已经确定了 } return max; }
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
[LeetCode] Container With Most WaterGiven n non-negative integers a1, a2, ..., a
/*中级思路以下我觉得分析有点问题*/ 中级思路, 这样的值 有两个性质, 不妨设 (i,a)为左边 (j,b)为右边为最大值, 1.若有坐标
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
Container With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum...
11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two...
1. Introduction ... Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
算法相关知识储备 LeetCode with Python
算法 Leetcode刷题手册 labuladong的算法小抄官方完整版
leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
703.Kth_Largest_Element_in_a_Stream数据流中的第K大元素【LeetCode单题讲解系列】
java;LeetCode前一百道;有题目;多重解法
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode-with-python3 ARRAY 1.两数之和 4.寻找两个有序数组的中位数 11.盛最多水的容器 26.删除排序数组中的重复项 15.三数之和 16.最接近的三数之和 27.移除元素 35.搜索插入位置 66.加一 88.合并两个有序数组
刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的记录,C++和Python两种语言的实现.zip刷leetcode的...
leetcode叫数 Leetcode Personal repository implement with Ruby 13. Roman to Integer 查表,通过从前往前筛选字符串,把代表的值一个个加起来 26. Remove Duplicates from Sorted Array 难度easy的题目。根据题目...
LeetCode 刷题笔记 with Java 51-100(暗黑版).pdf
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. ...