int ans = 0; int len = height.length; for (int i = 1; i < len - 1; i++) { int maxRight = 0; int maxLeft = 0; for (int right = i; right < len; right++) { maxRight = Math.max(maxRight, height[right]); }
for (int left = i; left >= 0; left--) { maxLeft = Math.max(maxLeft, height[left]); }
int ans = 0; int len = height.length; int[] leftMax = newint[len]; int[] rightMax = newint[len]; for (int i = 1; i < len - 1; i++) { leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]); }
for (int i = len - 2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]); }
for (int i = 1; i < len - 1; i++) { int min = Math.min(leftMax[i], rightMax[i]); ans += min > height[i] ? min - height[i] : 0; }
int len = height.length; int ans = 0; int leftMax = height[0]; int[] rightMax = newint[len]; for (int i = len - 2; i >= 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]); }
for (int i = 1; i < len - 1; i++) { leftMax = Math.max(leftMax, height[i]); int min = Math.min(leftMax, rightMax[i]); ans += min > height[i] ? min - height[i] : 0; }
return ans; }
上述代码的空间复杂度还是 O(n),如何才能把 rightMax 的数组也去掉呢?
因为从左往右处理到 i 下标时,左边的最大值 leftMax 是可信的,因为 rightMax 是从右往左遍历的,所以需要 rightMax 数组来记录右边最大值。
int len = height.length; int ans = 0; int left = 0; int right = len - 1; int leftMax = height[0]; int rightMax = height[right]; while (left < right) { if (height[left] < height[right]) { leftMax = Math.max(leftMax, height[left]); ans += leftMax - height[left]; left++; } else { rightMax = Math.max(rightMax, height[right]); ans += rightMax - height[right]; right--; } }
publicstaticinttrap_stack_opt(int[] height){ int ans = 0; Deque<Integer> stack = new LinkedList<Integer>(); int len = height.length; for (int i = 0; i < len; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int top = stack.pop(); if (stack.isEmpty()) { break; } int left = stack.peek(); int currWidth = i - left - 1; int currHeight = Math.min(height[left], height[i]) - height[top]; ans += currWidth * currHeight; } stack.push(i); }
return ans; }
复杂度分析:
时间复杂度:O(n)。
空间复杂度:O(n)。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)