# 1. Tóm tắt đề bài

Cho $n$ số là chiều cao của các "ô đất", đo lượng mưa đọng lại sau mỗi lần mưa.


### Giới hạn

$1 \le n \le 2*10^4$

# 2. Hướng giải

<details open>
<summary>Hint 1</summary>
Lưu giá trị cao nhất bên trái, phải.
</details>
<details open>
<summary>Hint 2</summary>
Xét đến việc nhét dần từng cột một.
</details>

# 3. Cách giải

Hint 1: Cách này update ans theo chiều dọc. Ta có thể lưu giá trị cao nhất bên trái, phải theo 2 cách: mảng dồn hoặc 2 con trỏ. Mảng dồn sẽ là mảng max dồn từ trái -> phải và phải -> trái, 2 con trỏ sẽ chạy từ 2 biên kéo dần vào giữa. Tại mỗi vị trí + vào $ans$ giá trị là $min($max trái, max phải$)$ - $height_i$

Hint 2: Cách này update ans theo chiều ngang. Lưu độ cao vào stack và duy trì sao cho trong stack là các giá trị giảm dần, top() là nhỏ nhất. Khi update, với mỗi stack.top() mà nhỏ hơn giá trị cần thêm vào, pop() ra + update giá trị: độ cao của nước * khoảng cách cột.

### Độ phức tạp thuật toán

Thời gian: $O(n)$

### Code:

Theo prefix, suffix:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> leftMax(n), rightMax(n);
        for (int i = 1; i < n; ++i) 
            leftMax[i] = max(height[i-1], leftMax[i-1]);
        for (int i = n-2; i >= 0; --i) 
            rightMax[i] = max(height[i+1], rightMax[i+1]);
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int waterLevel = min(leftMax[i], rightMax[i]);
            if (waterLevel >= height[i]) ans += waterLevel - height[i];
        }
        return ans;
    }
};

Theo stack:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ans=0;
        vector<int> st;

        for(int r=0; r<n; r++){
            while(!st.empty() && height[st.back()]<height[r]){
                int m=st.back();
                st.pop_back();

                if (st.empty()){
                break;
                }

                int l=st.back();
                int h= min(height[r]-height[m], height[l]-height[m]);
                int w= r-l-1;
                
                ans+=h*w;
            }
            st.push_back(r);
        }
        return ans;
    }
};

Theo 2 con trỏ:

class Solution {
public:
    int trap(vector<int>& height) {
        int i = 0, left_max = height[0], sum = 0;
        int j = height.size() - 1, right_max = height[j];
        while (i < j) {
            if (left_max <= right_max) {
                sum += (left_max - height[i]);
                i++;
                left_max = max(left_max, height[i]);
            } else {
                sum += (right_max - height[j]);
                j--;
                right_max = max(right_max, height[j]);
            }
        }
        return sum;
    }
};

# 4. Nhận xét

Sorry vì update muộn :pray: