leetcode-cn.com/problems/tr…

Answer:

  1. Taking example 1 of this problem as an example, the stack solution is to intuitively calculate the amount of water that can be held by all columns.

  1. The stack always stores indexes for the left edge of the bucket and the bottom of the bucket, for example, separately[1, 2],[3, 4, 5],[7, 8, 9].
  2. When the column is higher than the top of the stack, the element at the top of the stack is taken as the bottom of the bucket, and the remaining top of the stack is the left boundary, so as to form a layer of the bucket, and the water volume can be calculated, as shown in the figure below:

  1. Note that if the stack is empty after the element at the bottom of the bucket is removed from the stack, a bucket cannot be formed. For example, the index of the element at the bottom of the bucket is 0.
/ * * *@param {number[]} height
 * @return {number}* /
var trap = function (height) {
  let result = 0; // Store the total amount of water
  let stack = []; // The left edge and bottom of the bucket are stored in the stack

  // Traverses all the columns, which are used as the right boundary of the bucket before being pushed
  for (let right = 0; right < height.length; right++) {
    // If the right boundary is higher than the top element of the stack, it forms a bucket with the elements in the stack
    while (height[right] > height[stack[stack.length - 1]]) {
      // The top element of the stack is the bottom of the current bucket. Pop it up and calculate the height of the bottom of the bucket
      const bucketBottom = height[stack.pop()];

      // If the stack is empty, there is no bucket
      if(! stack.length) {break;
      }

      const left = stack[stack.length - 1]; // The remaining top element of the stack is the left edge of the bucket, which gets its index
      const leftHeight = height[left]; // Get the height of the left edge of the bucket
      const rightHeight = height[right]; // Get the height of the right edge of the bucket
      const bucketTop = Math.min(leftHeight, rightHeight); // The smaller value of the left and right edge of the bucket is the top height of the bucket
      const bucketHeight = bucketTop - bucketBottom; // The height of the bucket is the top minus the bottom of the bucket
      const width = right - left - 1; // The actual width of the bucket is the difference between the left and right sides minus one
      const area = width * bucketHeight; // Calculate the current water capacity of the bucket
      result += area; // Add water to the total
    }

    // The current right boundary can be used as the left boundary of the next bucket, so it needs to be pushed
    stack.push(right);
  }

  return result;
};
Copy the code