接雨水

42. 接雨水 - 力扣（LeetCode）

---

单调栈

初实现：

int trap(vector<int>& height) {
    int res = 0, pre = 0;
    stack<int> st;
    for (int i = 0; i < height.size(); i++) {
        if (height[i] >= pre) {
            while (!st.empty()) {
                res += pre - st.top();
                st.pop();
            }
            pre = height[i];
            st.push(pre);
            continue;
        } 
        if (height[i] <= st.top()) {
            st.push(height[i]);
            continue;
        }
        int tmp = 1;
        while (st.top() < height[i]) {
            res += height[i] - st.top();
            st.pop();
            tmp++;
        }
        for (int j = 0; j < tmp; j++) st.push(height[i]);
    }
    return res;
}

优化：

int trap(vector<int>& height) {
    int res = 0;
    stack<int> st;
    for (int i = 0; i < height.size(); i++) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int mid = st.top();
            st.pop();
            if (st.empty()) break;
            int left = st.top();
            int curWidth = i - left - 1;
            int curHeight = min(height[left], height[i]) - height[mid];
            res += curWidth * curHeight;
        }
        st.push(i);
    }
    return res;
}

栈中储存下标，使用过的mid直接出栈节省空间

两种实现均为$O(n) + O(n)$

双指针

维护两个指针left,right以及leftMax,rightMax。
由于计算雨水深度时，我们应该考虑左右Max中的较小者，所以我们移动Max较小一侧的指针，此时该侧的Max已然为水面所在。

int trap(vector<int>& height) {
	int res = 0;
	int left = 0, right = height.size() - 1;
	int leftMax = 0, rightMax = 0;
	while (left < right) {
		leftMax = max(leftMax, height[left]);
		rightMax = max(rightMax, height[right]);
		if (leftMax < rightMax) {
			res += leftMax - height[left];
			left++;
		} else {
			res += rightMax - height[right];
			right--;
		}
	}
	return res;
}

时间复杂度：$O(n)$
空间复杂度：$O(1)$