Merge pull request halfrost#148 from novahe/fix/84

halfrost · web-flow · commit 259eba0c849f · 2021-06-12T17:15:19.000+08:00
fix/84: easier to understand code
diff --git a/leetcode/0084.Largest-Rectangle-in-Histogram/84. Largest Rectangle in Histogram.go b/leetcode/0084.Largest-Rectangle-in-Histogram/84. Largest Rectangle in Histogram.go
@@ -1,32 +1,25 @@
 package leetcode
 
-import "fmt"
-
 func largestRectangleArea(heights []int) int {
-	maxArea, stack, height := 0, []int{}, 0
-	for i := 0; i <= len(heights); i++ {
-		if i == len(heights) {
-			height = 0
-		} else {
-			height = heights[i]
+	maxArea := 0
+	n := len(heights) + 2
+	// Add a sentry at the beginning and the end
+	getHeight := func(i int) int {
+		if i == 0 || n-1 == i {
+			return 0
 		}
-		if len(stack) == 0 || height >= heights[stack[len(stack)-1]] {
-			stack = append(stack, i)
-		} else {
-			tmp := stack[len(stack)-1]
-			fmt.Printf("1. tmp = %v stack = %v\n", tmp, stack)
-			stack = stack[:len(stack)-1]
-			length := 0
-			if len(stack) == 0 {
-				length = i
-			} else {
-				length = i - 1 - stack[len(stack)-1]
-				fmt.Printf("2. length = %v stack = %v i = %v\n", length, stack, i)
-			}
-			maxArea = max(maxArea, heights[tmp]*length)
-			fmt.Printf("3. maxArea = %v heights[tmp]*length = %v\n", maxArea, heights[tmp]*length)
-			i--
+		return heights[i-1]
+	}
+	st := make([]int, 0, n/2)
+	for i := 0; i < n; i++ {
+		for len(st) > 0 && getHeight(st[len(st)-1]) > getHeight(i) {
+			// pop stack
+			idx := st[len(st)-1]
+			st = st[:len(st)-1]
+			maxArea = max(maxArea, getHeight(idx)*(i-st[len(st)-1]-1))
 		}
+		// push stack
+		st = append(st, i)
 	}
 	return maxArea
 }
diff --git a/leetcode/0084.Largest-Rectangle-in-Histogram/84. Largest Rectangle in Histogram_test.go b/leetcode/0084.Largest-Rectangle-in-Histogram/84. Largest Rectangle in Histogram_test.go
@@ -40,6 +40,10 @@ func Test_Problem84(t *testing.T) {
 			para84{[]int{1, 1}},
 			ans84{2},
 		},
+		{
+			para84{[]int{2, 1, 2}},
+			ans84{3},
+		},
 	}
 
 	fmt.Printf("------------------------Leetcode Problem 84------------------------\n")
diff --git a/website/content/ChapterFour/0001~0099/0084.Largest-Rectangle-in-Histogram.md b/website/content/ChapterFour/0001~0099/0084.Largest-Rectangle-in-Histogram.md
@@ -41,37 +41,38 @@ Output: 10
 
 package leetcode
 
-import "fmt"
-
 func largestRectangleArea(heights []int) int {
-	maxArea, stack, height := 0, []int{}, 0
-	for i := 0; i <= len(heights); i++ {
-		if i == len(heights) {
-			height = 0
-		} else {
-			height = heights[i]
+	maxArea := 0
+	n := len(heights) + 2
+	// Add a sentry at the beginning and the end
+	getHeight := func(i int) int {
+		if i == 0 || n-1 == i {
+			return 0
 		}
-		if len(stack) == 0 || height >= heights[stack[len(stack)-1]] {
-			stack = append(stack, i)
-		} else {
-			tmp := stack[len(stack)-1]
-			fmt.Printf("1. tmp = %v stack = %v\n", tmp, stack)
-			stack = stack[:len(stack)-1]
-			length := 0
-			if len(stack) == 0 {
-				length = i
-			} else {
-				length = i - 1 - stack[len(stack)-1]
-				fmt.Printf("2. length = %v stack = %v i = %v\n", length, stack, i)
-			}
-			maxArea = max(maxArea, heights[tmp]*length)
-			fmt.Printf("3. maxArea = %v heights[tmp]*length = %v\n", maxArea, heights[tmp]*length)
-			i--
+		return heights[i-1]
+	}
+	st := make([]int, 0, n/2)
+	for i := 0; i < n; i++ {
+		for len(st) > 0 && getHeight(st[len(st)-1]) > getHeight(i) {
+			// pop stack
+			idx := st[len(st)-1]
+			st = st[:len(st)-1]
+			maxArea = max(maxArea, getHeight(idx)*(i-st[len(st)-1]-1))
 		}
+		// push stack
+		st = append(st, i)
 	}
 	return maxArea
 }
 
+func max(a int, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+
 ```
 
 
