fd

dingjikerbo · dingjikerbo · commit 64dcebfd50ef · 2017-12-11T16:42:31.000+08:00
diff --git a/doc/木桶原理.md b/doc/木桶原理.md
@@ -0,0 +1,3 @@
+287. Find the Duplicate Number
+220. Contains Duplicate III
+164. Maximum Gap
diff --git a/solution/src/main/java/com/inuker/solution/ClosestBinarySearchTreeValueII.java b/solution/src/main/java/com/inuker/solution/ClosestBinarySearchTreeValueII.java
@@ -14,7 +14,6 @@
 /**
  * 有三种解法：
  * 2，中序遍历两遍二叉树，不过每次都会中途退出，构成双栈，一个是大于target，一个是小于target，然后依次出栈满k为止，复杂度O(n + k)
- * 3，中序完整遍历一遍二叉树，依次将节点加入优先级队列，按与target的差排序，选前k个，复杂度O(nlgk)
  */
 public class ClosestBinarySearchTreeValueII {
 
diff --git a/solution/src/main/java/com/inuker/solution/FindTheDuplicateNumber.java b/solution/src/main/java/com/inuker/solution/FindTheDuplicateNumber.java
@@ -28,7 +28,7 @@ public int findDuplicate(int[] nums) {
             }
 
             /**
-             * 如果count>mid，说明元素个数count比桶数mid还打，则可以肯定重复的数在[1,mid]中
+             * 如果count>mid，说明元素个数count比桶数mid还大，则可以肯定重复的数在[1,mid]中
              * 但是count<=mid就能确定重复的数肯定不在[1,mid]中么？不一定吧，接下来推理一下：
              * 我们看右边的一半，[mid+1,n]区间的数有n+1-count个，可见元素有n+1-count个，桶有n-mid个，而count<=mid等价于count-1<mid，
              * 因此元素个数大于桶数，右区间一定有重复的数，由于题目已经限定只有一个重复数，因此只能在右区间
diff --git a/solution/src/main/java/com/inuker/solution/LargestRectangleInHistogram.java b/solution/src/main/java/com/inuker/solution/LargestRectangleInHistogram.java
@@ -29,7 +29,10 @@ public int largestRectangleArea(int[] heights) {
         return max;
     }
 
-    /** 注意栈中的是index，不是高度 */
+    /** 注意栈中的是index，不是高度
+     *  栈保持递增，当出现小于栈顶的元素时，意味着可以计算栈顶可以延伸的矩形面积了
+     *  其左边界是次栈顶，右边界是当前元素
+     */
     public int largestRectangleArea2(int[] heights) {
         int max = 0;
         Stack<Integer> stack = new Stack<Integer>();
@@ -40,6 +43,10 @@ public int largestRectangleArea2(int[] heights) {
             } else {
                 int top = stack.pop();
                 int left = stack.isEmpty() ? 0 : stack.peek() + 1;
+                /**
+                 * top两边都是比top高的
+                 * [left,i-1]
+                 */
                 max = Math.max(max, heights[top] * (i - 1 - left + 1));
             }
         }

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,3 @@`
	`1`	`+287. Find the Duplicate Number`
	`2`	`+220. Contains Duplicate III`
	`3`	`+164. Maximum Gap`
Original file line number	Diff line number	Diff line change
`@@ -28,7 +28,7 @@ public int findDuplicate(int[] nums) {`
`28`	`28`	`}`
`29`	`29`
`30`	`30`	`/**`
`31`		`- * 如果count>mid，说明元素个数count比桶数mid还打，则可以肯定重复的数在[1,mid]中`
	`31`	`+ * 如果count>mid，说明元素个数count比桶数mid还大，则可以肯定重复的数在[1,mid]中`
`32`	`32`	`* 但是count<=mid就能确定重复的数肯定不在[1,mid]中么？不一定吧，接下来推理一下：`
`33`	`33`	`* 我们看右边的一半，[mid+1,n]区间的数有n+1-count个，可见元素有n+1-count个，桶有n-mid个，而count<=mid等价于count-1<mid，`
`34`	`34`	`* 因此元素个数大于桶数，右区间一定有重复的数，由于题目已经限定只有一个重复数，因此只能在右区间`