Nov 20, 2024

LeetCode刷题笔记 - 栈与队列

Xinyu Li

GrindingLeetCode

900 Words 4 Minutes, 5 Seconds

2024-11-20 19:41 -0800

单调队列

347. Top K Frequent Elements

Iterate over the array to compute frequency of each element, and use a max heap (priority queue) to record top k most frequent elements.

单调栈

739. Daily Temperatures

一个自底向上单调递增的栈，储存(day, temperature)。入栈前先把所有小于当前温度的天弹出，同时记录这些天和当前天的差距。

496. Next Greater Element I

Constraint: Solution must be O(nums1.length + nums2.length)

503. Next Greater Element II

For array nums, duplicate nums to double_nums = nums + nums, and do the monotone stack thing as in 496.

42. Trapping Rain Water

Double pointer (more intuitive)

Compute the amount of water trapped at each column.

For column i, the amount of water trapped at column i is determined by the shorter bar between the tallest bar on the left and the taller bar on the right. That is,

trappedWater = min(max(heights[:i]), max(heights[i+1:])) - heights[i];

For example, consider column 3 of height 1, column 4 is of height inf, column 0, 1, 2 are of height 3, 6, 4. The tallest left bar has height 6, and tallest right bar has height inf. So min(max([3,6,4]), inf) - 1 = 5 water can be trapped at column 3.

To avoid redundent computation, we first compuet maxLeft and maxRight for all columns, then compute the amount of water trapped at each column.

int trap(vector<int>& height) {
    int n = height.size();
    vector<int> maxLeft(n);
    vector<int> maxRight(n);

    maxLeft[0] = height[0];
    for (int i = 1; i < n; i++) {
        maxLeft[i] = max(height[i], maxLeft[i-1]);
    }

    maxRight[n-1] = height[n-1];
    for (int i = n-2; i >= 0; i--) {
        maxRight[i] = max(height[i], maxRight[i+1]);
    }

    int count = 0;
    for (int i = 1; i < n-1; i++) {
        count += min(maxLeft[i], maxRight[i]) - height[i];
    }

    return count;
}

Prev solution:

  1. Scan from left to right to find all ponds with left bar <= right bar;

  2. Scan from right to left to find all ponds with left bar > right bar;

  3. Sum the two results to get total pond size.

Don’t really need a monotone stack…

84. Largest Rectangle in Histogram

For bar i, consider the max rectangle that contains bar i. This rectangle must consist of consecutive bars where each bar is no shorter than bar i.

首先，最大长方形一定会刚好包含一根柱子，既高度等于某一根柱子。这是因为任何符合提议的长方形，其高度不大于所包含的柱子。假如最大长方形的高度小于所有被包含的长方形，那么在其基础上往上扩展一格仍符合题意，且面积更大。

由此可知，我们只需要对每一个柱子，考虑完整包含它的最大长方形就可以。

对于柱子i，刚好包含它的最大长方形由一连串经过柱子i，且高度不小于柱子i的柱子组成。它的高度和柱子i相同，长度则是由柱子i左右第一根高度小于i的柱子决定。

为防止重复计算，我们提前计算minLeft和minRight。在计算minLeft[k]时，我们可以通过已经计算的minLeft[:k]简化计算。

由此可得算法

int largestRectangleArea(vector<int>& heights) {
    int n = heights.size();
    // minLeft[i] is the index of first bar to the left of bar i w/ height < bar i
    // we prepend and append a 0 to heights, so that such bar must exists left and right.
    vector<int> minLeft(n+2);
    vector<int> minRight(n+2);
    heights.insert(heights.begin(), 0);
    heights.push_back(0);

    minLeft[0] = 0;
    for (int curIdx = 1; curIdx < n+1; curIdx++) {
        int leftIdx = curIdx-1;
        while (leftIdx > 0) {
            if (heights[leftIdx] < heights[curIdx]) {
                break;
            }
            leftIdx = minLeft[leftIdx];
        }
        minLeft[curIdx] = leftIdx;
        // cout << leftIdx << ", ";
    }
    // cout << endl;

    minRight[n+1] = n+1;
    for (int curIdx = n; curIdx >= 0; curIdx--) {
        int rightIdx = curIdx+1;
        while (rightIdx < n+1) {
            if (heights[rightIdx] < heights[curIdx]) {
                break;
            }
            rightIdx = minRight[rightIdx];
        }
        minRight[curIdx] = rightIdx;
        // cout << rightIdx << ", ";
    }
    // cout << endl;

    int maxRect = 0;
    for (int i = 1; i < n+1; i++) {
        int curRect = (minRight[i] - minLeft[i] - 1) * heights[i];
        maxRect = max(maxRect, curRect);
    }
    return maxRect;
}

See Also