42. 接雨水

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。

方法一： 暴力解法

class Solution {public int trap(int[] height) {int sum = 0;for (int i = 0; i < height.length; i++) {// 第一個柱子和最后一個柱子不接雨水if (i==0 || i== height.length - 1) continue;int rHeight = height[i]; // 記錄右邊柱子的最高高度int lHeight = height[i]; // 記錄左邊柱子的最高高度for (int r = i+1; r < height.length; r++) {if (height[r] > rHeight) rHeight = height[r];}for (int l = i-1; l >= 0; l--) {if(height[l] > lHeight) lHeight = height[l];}int h = Math.min(lHeight, rHeight) - height[i];if (h > 0) sum += h;}return sum;}
}

這段代碼是用于解決「接雨水」問題的Java實現。給定一個數組 height，其中 height[i] 表示第 i 個位置的柱子的高度，目標是計算在這個直方圖中能接多少雨水。這個問題的關鍵在于找到每個位置左右兩邊最高的柱子，以此來確定能夠接住的雨水量。

代碼解析

1. 初始化:

   • 創建一個變量 sum，用于累計接住的雨水總量。

2. 遍歷并計算雨水量:

   • 遍歷數組 height 中的每個元素，除了第一個和最后一個元素（因為它們無法形成封閉的空間來接雨水）。
   • 對于當前遍歷到的元素 height[i]：
     • 計算右側最高柱子的高度 rHeight 和左側最高柱子的高度 lHeight。
     • 可以接住的雨水量取決于左右兩邊柱子中較低的那個與當前柱子高度的差值，即 Math.min(lHeight, rHeight) - height[i]。
     • 如果這個差值大于0，說明可以接住雨水，將其累加到 sum 中。

3. 返回結果:

   • 返回累計的雨水總量 sum。

時間復雜度和空間復雜度

• 時間復雜度: O(n^2)，其中 n 是數組 height 的長度。這是因為在遍歷數組的過程中，對于每個元素，都需要再次遍歷其左側和右側來尋找最高柱子，導致時間復雜度較高。
• 空間復雜度: O(1)，除了輸入數組 height，代碼中沒有使用額外的數據結構，僅使用了幾個變量進行計算。

總結

雖然這段代碼能夠正確解決接雨水問題，但是其時間復雜度較高，為 O(n^2)，在處理大數據量時效率低下。為了提高效率，可以采用動態規劃或雙指針技術，將時間復雜度降低到 O(n)。例如，可以預先計算每個位置左邊最大高度和右邊最大高度，或者使用雙指針從兩邊向中間逼近，這樣可以避免對每個元素進行二次遍歷，顯著提升算法性能。在實際應用中，優化算法的時間復雜度是提高程序運行效率的關鍵，特別是在處理大規模數據時尤為重要。

方法二：雙指針

class Solution {public int trap(int[] height) {int length = height.length;if (length <= 2) return 0;int[] maxLeft = new int[length];int[] maxRight = new int[length];// 記錄每個柱子左邊柱子最大高度maxLeft[0] = height[0];for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);// 記錄每個柱子右邊柱子最大高度maxRight[length - 1] = height[length - 1];for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);// 求和int sum = 0;for (int i = 0; i < length; i++) {int count = Math.min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}
}

這段代碼是用于解決「接雨水」問題的另一種Java實現，相較于之前的實現，它使用了動態規劃的思想來優化算法的時間復雜度。目標依然是計算在一個直方圖中能接多少雨水，但是這次通過預計算每個位置左右兩邊的最高柱子高度，避免了對每個位置的二次遍歷，從而提高了算法效率。

代碼解析

1. 初始化:

   • 創建兩個數組 maxLeft 和 maxRight，分別用于存儲每個位置左側最大高度和右側最大高度。
   • 創建變量 sum，用于累計接住的雨水總量。

2. 計算左側最大高度:

   • 初始化 maxLeft[0] 為 height[0]，即數組的第一個元素。
   • 從左到右遍歷數組，更新 maxLeft 數組中每個位置左側的最大高度。

3. 計算右側最大高度:

   • 初始化 maxRight[length - 1] 為 height[length - 1]，即數組的最后一個元素。
   • 從右到左遍歷數組，更新 maxRight 數組中每個位置右側的最大高度。

4. 計算雨水量:

   • 遍歷數組，對于每個位置 i：
     • 計算可以接住的雨水量為左右兩邊柱子中較低的那個與當前柱子高度的差值，即 Math.min(maxLeft[i], maxRight[i]) - height[i]。
     • 如果這個差值大于0，說明可以接住雨水，將其累加到 sum 中。

5. 返回結果:

   • 返回累計的雨水總量 sum。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 height 的長度。這是因為算法分別進行了三次遍歷：一次計算左側最大高度，一次計算右側最大高度，一次計算雨水量，每次遍歷的時間復雜度均為 O(n)。
• 空間復雜度: O(n)，需要兩個大小為 n 的數組 maxLeft 和 maxRight 來存儲中間結果。

總結

這段代碼通過預計算每個位置左右兩邊的最高柱子高度，避免了對每個位置進行二次遍歷，從而將時間復雜度從 O(n^2) 優化到了 O(n)，顯著提升了算法效率。這種方法在處理大數據量時尤其重要，能夠確保算法在合理時間內完成計算。在實際應用中，動態規劃是一種常用的優化算法時間復雜度的技術，通過將問題分解成更小的子問題并緩存子問題的結果，可以避免重復計算，提高算法效率。

方法三：雙指針優化

class Solution {public int trap(int[] height) {if (height.length <= 2) {return 0;}// 從兩邊向中間尋找最值int maxLeft = height[0], maxRight = height[height.length - 1];int l = 1, r = height.length - 2;int res = 0;while (l <= r) {// 不確定上一輪是左邊移動還是右邊移動，所以兩邊都需更新最值maxLeft = Math.max(maxLeft, height[l]);maxRight = Math.max(maxRight, height[r]);// 最值較小的一邊所能裝的水量已定，所以移動較小的一邊。if (maxLeft < maxRight) {res += maxLeft - height[l ++];} else {res += maxRight - height[r --];}}return res;}
}

這段代碼是用于解決「接雨水」問題的又一種Java實現，它采用了雙指針技術，從數組的兩端向中間逼近，逐步計算能接住的雨水量。這種方法避免了預處理數組或多次遍歷，使得算法的時間復雜度和空間復雜度均得到優化。

代碼解析

1. 初始化:

   • 檢查數組長度，如果長度小于等于2，直接返回0，因為至少需要三個柱子才能形成封閉空間來接雨水。
   • 初始化兩個指針 l 和 r，分別指向數組的第二個元素和倒數第二個元素。
   • 初始化兩個變量 maxLeft 和 maxRight，分別記錄左側和右側當前遇到的最大高度。

2. 雙指針逼近:

   • 使用循環，直到 l 和 r 相遇或交錯。
   • 在每次循環中，更新 maxLeft 和 maxRight 的值，確保它們始終存儲從開始位置到當前指針位置的最大高度。
   • 比較 maxLeft 和 maxRight 的值：
     • 如果 maxLeft 小于 maxRight，意味著左側的高度不足以阻擋雨水，因此左側的雨水量為 maxLeft - height[l]，將其累加到結果變量 res 中，并將左側指針 l 向右移動一位。
     • 否則，右側的高度不足以阻擋雨水，右側的雨水量為 maxRight - height[r]，將其累加到結果變量 res 中，并將右側指針 r 向左移動一位。

3. 返回結果:

   • 循環結束后，返回累計的雨水總量 res。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 height 的長度。這是因為雙指針技術確保了每個元素僅被訪問一次。
• 空間復雜度: O(1)，除了輸入數組 height，代碼中只使用了幾個變量進行計算，沒有額外的數據結構。

總結

這段代碼通過雙指針技術實現了對「接雨水」問題的有效求解，避免了預處理數組或多次遍歷的高時間復雜度，同時在空間復雜度方面也得到了優化。雙指針技術是一種常見的算法技巧，適用于多種問題，如尋找兩個有序數組的中位數、求解兩數之和等。在實際應用中，掌握雙指針技術能夠幫助我們更高效地解決許多類型的問題，特別是那些涉及到數組或列表的遍歷和比較的問題。

方法四：單調棧

class Solution {public int trap(int[] height){int size = height.length;if (size <= 2) return 0;// in the stack, we push the index of array// using height[] to access the real heightStack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int index = 1; index < size; index++){int stackTop = stack.peek();if (height[index] < height[stackTop]){stack.push(index);}else if (height[index] == height[stackTop]){// 因為相等的相鄰墻，左邊一個是不可能存放雨水的，所以pop左邊的index, push當前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint heightAtIdx = height[index];while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){int mid = stack.pop();if (!stack.isEmpty()){int left = stack.peek();int h = Math.min(height[left], height[index]) - height[mid];int w = index - left - 1;int hold = h * w;if (hold > 0) sum += hold;stackTop = stack.peek();}}stack.push(index);}}return sum;}
}

這段代碼是用于解決「接雨水」問題的另一種Java實現，它采用了單調棧的策略。單調棧是一種數據結構，可以用來快速找到數組中某個元素左側或右側的下一個更大或更小的元素，非常適合解決接雨水問題，因為要確定每個位置可以接住的雨水量，關鍵在于找到其左右兩側的最高柱子。

代碼解析

1. 初始化:

   • 檢查數組長度，如果長度小于等于2，直接返回0。
   • 創建一個單調棧 stack，用于存儲數組元素的下標。
   • 初始化一個變量 sum，用于累計接住的雨水總量。

2. 遍歷并維護單調棧:

   • 遍歷數組 height 中的每個元素。
   • 對于當前遍歷到的元素 height[index]：
     • 如果當前元素小于棧頂元素對應的值，將當前下標 index 入棧。
     • 如果當前元素等于棧頂元素對應的值，將棧頂元素彈出，因為相等的相鄰墻，左邊一個是不可能存放雨水的，然后將當前下標 index 入棧。
     • 如果當前元素大于棧頂元素對應的值，進入一個循環：
       • 彈出棧頂元素，直到棧為空或者棧頂元素對應的值不小于當前元素。
       • 對于每次彈出的元素，如果棧不為空，計算可以接住的雨水量，即左右兩邊柱子中較低的那個與彈出元素高度的差值乘以寬度（當前下標與棧頂下標的距離減1），將其累加到結果變量 sum 中。

3. 返回結果:

   • 返回累計的雨水總量 sum。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 height 的長度。每個元素至多被放入和彈出棧一次。
• 空間復雜度: O(n)，需要一個大小為 n 的單調棧 stack。

總結

這段代碼通過使用單調棧，有效地解決了接雨水問題，避免了多次遍歷數組，提高了算法效率。單調棧在處理這類問題時表現出色，能夠快速找到特定條件下下一個更大或更小的元素，是解決與單調性相關的數組或序列問題的常用工具。在實際應用中，掌握單調棧的使用方法能夠幫助解決一系列經典問題，提高代碼效率和性能。

84. 柱狀圖中最大的矩形

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。
輸入：heights = [2,1,5,6,2,3]
輸出：10
解釋：最大的矩形為圖中紅色區域，面積為 10

輸入： heights = [2,4]
輸出： 4

方法一：暴力解法

class Solution {public int largestRectangleArea(int[] heights) {int length = heights.length;int[] minLeftIndex = new int [length];int[] minRightIndex = new int [length];// 記錄左邊第一個小于該柱子的下標minLeftIndex[0] = -1 ;for (int i = 1; i < length; i++) {int t = i - 1;// 這里不是用if，而是不斷向右尋找的過程while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];minLeftIndex[i] = t;}// 記錄每個柱子右邊第一個小于該柱子的下標minRightIndex[length - 1] = length;for (int i = length - 2; i >= 0; i--) {int t = i + 1;while(t < length && heights[t] >= heights[i]) t = minRightIndex[t];minRightIndex[i] = t;}// 求和int result = 0;for (int i = 0; i < length; i++) {int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);result = Math.max(sum, result);}return result;}
}

這段代碼是用于解決「最大矩形」問題的Java實現，其目標是在由非負整數構成的直方圖中尋找最大矩形面積。給定一個數組 heights，其中 heights[i] 表示第 i 個位置的柱子的高度，問題是要找出直方圖中最大的矩形面積。

代碼解析

1. 初始化:

   • 創建兩個數組 minLeftIndex 和 minRightIndex，分別用于存儲每個柱子左側第一個小于它的柱子的下標和右側第一個小于它的柱子的下標。
   • 創建變量 result，用于存儲最大的矩形面積。

2. 計算左側最小下標:

   • 初始化 minLeftIndex[0] 為 -1，即數組的最左側。
   • 從左到右遍歷數組，對于每個位置 i，使用一個變量 t 來追蹤左側第一個小于 heights[i] 的柱子的下標。如果當前位置的柱子高度小于等于左側柱子的高度，就繼續向左尋找，直到找到一個小于它的柱子為止，或者到達數組邊界。

3. 計算右側最小下標:

   • 初始化 minRightIndex[length - 1] 為 length，即數組的最右側。
   • 從右到左遍歷數組，對于每個位置 i，使用一個變量 t 來追蹤右側第一個小于 heights[i] 的柱子的下標。如果當前位置的柱子高度小于等于右側柱子的高度，就繼續向右尋找，直到找到一個小于它的柱子為止，或者到達數組邊界。

4. 計算最大矩形面積:

   • 遍歷數組，對于每個位置 i，計算以該柱子為底邊的矩形面積，即 heights[i] 乘以寬度，寬度為 minRightIndex[i] - minLeftIndex[i] - 1。
   • 更新 result，使其始終保持最大面積的值。

5. 返回結果:

   • 返回最終計算出的最大矩形面積 result。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 heights 的長度。算法分別進行了三次遍歷：一次計算左側最小下標，一次計算右側最小下標，一次計算最大矩形面積，每次遍歷的時間復雜度均為 O(n)。
• 空間復雜度: O(n)，需要兩個大小為 n 的數組 minLeftIndex 和 minRightIndex 來存儲中間結果。

總結

這段代碼通過預計算每個柱子左右兩側第一個小于它的柱子的下標，避免了對每個位置進行多次遍歷來尋找最優解，從而將時間復雜度從 O(n^2) 優化到了 O(n)，顯著提升了算法效率。這種方法在處理大數據量時尤其重要，能夠確保算法在合理時間內完成計算。在實際應用中，這種通過預處理數據來加速計算的策略是解決復雜問題的常見手段，通過將問題分解成更小的子問題并提前計算關鍵信息，可以避免重復計算，提高算法效率。

方法二：單調棧

class Solution {int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>();// 數組擴容，在頭和尾各加入一個元素int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int index = 0; index < heights.length; index++){newHeights[index + 1] = heights[index];}heights = newHeights;st.push(0);int result = 0;// 第一個元素已經入棧，從下標1開始for (int i = 1; i < heights.length; i++) {// 注意heights[i] 是和heights[st.top()] 比較 ，st.top()是下標if (heights[i] > heights[st.peek()]) {st.push(i);} else if (heights[i] == heights[st.peek()]) {st.pop(); // 這個可以加，可以不加，效果一樣，思路不同st.push(i);} else {while (heights[i] < heights[st.peek()]) { // 注意是whileint mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];result = Math.max(result, w * h);}st.push(i);}}return result;}
}

這段代碼是用于解決「最大矩形」問題的另一種Java實現，它采用了單調棧的策略。問題的核心是在由非負整數構成的直方圖中尋找最大矩形面積。給定一個數組 heights，其中 heights[i] 表示第 i 個位置的柱子的高度，目標是找到直方圖中最大的矩形面積。

代碼解析

1. 初始化與數組擴容:

   • 創建一個單調棧 st，用于存儲數組元素的下標。
   • 為了便于處理邊界條件，首先對數組 heights 進行擴容，即在頭部和尾部各添加一個高度為0的虛擬柱子，這樣可以簡化后續的邏輯處理。

2. 遍歷并維護單調棧:

   • 初始化棧，將第一個元素的下標 0 入棧。
   • 從下標 1 開始遍歷數組 heights。
   • 對于當前遍歷到的元素 heights[i]：
     • 如果當前元素高度大于棧頂元素對應的值，將當前下標 i 入棧。
     • 如果當前元素高度等于棧頂元素對應的值，可以將棧頂元素彈出，再將當前下標 i 入棧（注：這里彈出棧頂元素并非必要步驟，但不影響最終結果，僅影響棧內元素的分布）。
     • 如果當前元素高度小于棧頂元素對應的值，進入一個循環：
       • 不斷彈出棧頂元素，直到棧為空或者棧頂元素對應的值不大于當前元素高度。
       • 對于每次彈出的元素，計算可以形成的矩形面積，即高度乘以寬度（當前下標 i 減去棧頂下標再減1），更新最大面積 result 的值。
       • 循環結束后，將當前下標 i 入棧。

3. 返回結果:

   • 返回計算出的最大矩形面積 result。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 heights 的長度。每個元素至多被放入和彈出棧一次。
• 空間復雜度: O(n)，需要一個大小為 n 的單調棧 st。

總結

這段代碼通過使用單調棧，有效地解決了最大矩形問題，避免了多次遍歷數組來尋找最優解，提高了算法效率。單調棧在處理這類問題時表現出色，能夠快速找到特定條件下下一個更大或更小的元素，是解決與單調性相關的數組或序列問題的常用工具。在實際應用中，掌握單調棧的使用方法能夠幫助解決一系列經典問題，提高代碼效率和性能。通過適當的數據結構和算法設計，如這里的單調棧，可以顯著減少時間復雜度，使算法在處理大規模數據時也能保持高效。

方法三：單調棧精簡

class Solution {public int largestRectangleArea(int[] heights) {int[] newHeight = new int[heights.length + 2];System.arraycopy(heights, 0, newHeight, 1, heights.length);newHeight[heights.length+1] = 0;newHeight[0] = 0;Stack<Integer> stack = new Stack<>();stack.push(0);int res = 0;for (int i = 1; i < newHeight.length; i++) {while (newHeight[i] < newHeight[stack.peek()]) {int mid = stack.pop();int w = i - stack.peek() - 1;int h = newHeight[mid];res = Math.max(res, w * h);}stack.push(i);}return res;}
}

這段代碼是用于解決「最大矩形」問題的Java實現，其目標是在由非負整數構成的直方圖中找到具有最大面積的矩形。給定一個數組 heights，其中 heights[i] 表示直方圖中第 i 個柱子的高度，算法的任務是確定這個直方圖中可以形成的具有最大面積的矩形。

代碼解析

1. 初始化與數組擴容:

   • 創建一個新數組 newHeight，長度為原數組 heights 長度加上2，這樣做是為了簡化邊界條件的處理。
   • 將原數組 heights 的內容復制到 newHeight 的中間部分，同時在 newHeight 的頭部和尾部各添加一個高度為0的元素。這樣可以確保算法在處理邊界柱子時不會出現下標越界的情況。

2. 創建單調棧:

   • 創建一個單調棧 stack，用于存儲柱子的下標，初始時將 newHeight 的第一個元素下標 0 入棧。

3. 遍歷并維護單調棧:

   • 從下標 1 開始遍歷 newHeight。
   • 對于當前遍歷到的元素 newHeight[i]：
     • 如果當前元素的高度小于棧頂元素對應的高度，即 newHeight[i] < newHeight[stack.peek()]，則：
       • 進入一個循環，持續彈出棧頂元素直到棧為空或當前元素高度大于等于棧頂元素高度。
       • 對于每次彈出的元素，計算可以形成的矩形面積，即高度乘以寬度（當前下標 i 減去棧頂下標再減1），并更新最大面積 res 的值。
     • 無論當前元素高度與棧頂元素高度的比較結果如何，都將當前下標 i 入棧。

4. 返回結果:

   • 算法完成后，返回計算出的最大矩形面積 res。

時間復雜度和空間復雜度

• 時間復雜度: O(n)，其中 n 是數組 heights 的長度。每個元素至多被放入和彈出棧一次。
• 空間復雜度: O(n)，需要一個大小為 n 的單調棧 stack 和一個長度為 heights.length + 2 的數組 newHeight。

總結

這段代碼通過使用單調棧策略，有效地解決了最大矩形問題，避免了多次遍歷數組來尋找最優解，提高了算法效率。單調棧在這里用于快速找到每個柱子左側和右側第一個低于它的柱子，進而計算出以該柱子為高度的最大矩形面積。在實際應用中，單調棧是一種非常實用的數據結構，尤其適合處理與單調性有關的問題，如尋找下一個更大或更小的元素、計算直方圖最大矩形面積等。通過巧妙地利用單調棧，可以顯著降低算法的時間復雜度，使程序在處理大規模數據時仍能保持高效。