Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

84. Largest Rectangle in Histogram

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int sz = heights.size();
        vector<int> left(sz);
        vector<int> right(sz);
        left[0] = -1;
        right.back() = sz;
        for(int i = 1; i < sz; ++i)
        {
            int p = i - 1;
            while(p >= 0 && heights[p] >= heights[i])
                p = left[p];
            left[i] = p;
        }
        
        for(int i = sz - 2; i >= 0; -- i)
        {
            int p = i + 1;
            while(p < sz && heights[p] >= heights[i])
                p = right[p];
            right[i] = p;
        }
        
        int ret = 0;
        for(int i = 0; i < sz; ++i)
            ret = max(ret, heights[i] * (right[i] - left[i] - 1));
        return ret;
    }
};

每个位置的最大矩形是其(right - left) * cur_height，而左边可以通过遍历查找离他最远且值>=他本身的坐标，右边也可通过遍历查找离他最远的且一路上值>=它本身的坐标。但如果对每个坐标都进行一次左右遍历就会消耗太多计算量。

此时可以采用dp

设想，对于先前查找过的元素，比如p<i，如果p是符合条件heights[p] >= heights[i]的，那么p的左边界也必然是符合这个条件的，由此可以进行坐标的跳跃，将下一迭代的p = left[p]，道理则依次。所以每个查找都可以运用到之前到查找的信息。总体来说仅仅为O(n)，对于右边界来说则同理。

使用stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(-1); // 这里的-1是为了在最后计算所有横跨许多块的长度
        stack<int> s;
        int ret = 0;
        for(int i = 0; i < heights.size(); ++i)
        {
            while(!s.empty() && heights[i] < heights[s.top()])
            {
                auto h = heights[s.top()];
                s.pop();
                ret = max(ret, (i - (s.empty() ? -1 : s.top()) - 1) * h);
            }
            s.push(i);
        }
        return ret;
    }
};

维持stack为上升序列，每碰到之前比他大的就pop掉，因为你如果比他小了，那么对于你这个柱子来说的最大矩形的高度必定受限于你而不是他，之前所有比你大的pop掉后的真空区域就是这个的面积。而循环中的i为右界，取不到，stack.top()，为左界，也取不到，中间的就是所有比你大的。上升队列的每2个之间都会有一个真空区域，而面积必定为区域宽度x右边。 1620478443908.png

why stack?

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

85. Maximal Rectangle

太难理解了！！！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty())
            return 0;
        int maxA = 0;
        int n = matrix[0].size();
        // 每个点具有三个信息，左界，右界和高度
        vector<int> left(n, 0); 
        vector<int> right(n, n);
        vector<int> height(n, 0);
        for(int i = 0; i < matrix.size(); ++i)
        {
            int curL = 0, curR = n;
            for(int j = n - 1; j >= 0; --j)
            {
                if(matrix[i][j] == '1')
                    right[j] = min(right[j], curR);
                else
                {
                    right[j] = n;
                    curR = j;
                }
            }
            
            for(int j = 0; j < n; ++j)
            {
                if(matrix[i][j] == '1')
                {
                    ++height[j];
                    left[j] = max(curL, left[j]);
                }else
                {
                    height[j] = 0;
                    left[j] = 0;
                    curL = j + 1;
                }
                maxA = max(maxA, (right[j] - left[j]) * height[j]);
            }
        }
        return maxA;
    }
};

所有信息会进行传递

出现如下这种时[1][4]元素左界会有上面那个来界定，高度也会随之更新，但不必担心由此扰乱更大的矩形的判断，因为这个元素处curR为5，若这个竖着的矩形不是最大矩形，那么这个右界限会保持住传给他的左边隔壁，如果他左边隔壁也不要这个右界限，说明左边隔壁也继承了上一层的信息。那么继续传递过去，如果都不要，那么2是有2层的，不要也无所谓了，肯定比一层长。同理左界限也会传递。由此这一层中的每个元素都会记录他本身所在的矩形，并且是所有局部最大矩形。 

1
2
000010
011111
还是有点绕

明天去画个图

1620472343565.png 
1
2
3
4
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Posted on Edited on In Disqus:
Symbols count in article: 765 Reading time ≈ 1 mins.

239. Sliding Window Maximum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ret;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(!dq.empty() && dq.front() < i - k + 1)
                dq.pop_front();
            while(!dq.empty() && nums[dq.back()] < nums[i])
                dq.pop_back();
            dq.push_back(i);
            if(i >= k - 1)
                ret.push_back(nums[dq.front()]);
        }
        return ret;
    }
};

使用双向序列，先加入的在序列头，后加入的在序列尾。当序列头中坐标小于i-k+1时，这个元素对于目前的窗口已经没用了，将其舍弃掉。对于其他的元素，从尾部移掉所有小于当前值的元素，因为对于a[x] < a[i] && x < i，后面的窗口可以使用a[i]而不是a[x]。由此一来序列头永远都是当前窗口最大项。

为什么从尾部移除小于当前值的元素而不是从头部呢？ > 只需要想清楚要移除的是a[x] < a[i] && x < i，因此在插入一个元素前把前面的无用项全都丢了再插入，当然是从后面开始往前删。a[x] > a[i] && x < i的元素对后面是有用的

1620305144539.png

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

128. Longest Consecutive Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty())
            return 0;
        sort(nums.begin(), nums.end());
        int ret = 1;
        int tmp = 1;
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] != nums[i - 1])
            {
                if(nums[i] == nums[i - 1] + 1)
                    ++tmp;
                else
                {
                    ret = max(ret, tmp);
                    tmp = 1;
                }
            }
        }
        return max(ret, tmp);
    }
};

T(n) : O(nlogn)
S(n) : O(1)

排序后，跳过相同的，计算多个子串，如果不相等，就从头开始计算

hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty())
            return 0;
        unordered_set<int> set;
        for(auto& num : nums)
        {
            set.insert(num);
        }
        int ret = 1;
        for(auto& num : nums)
        {
            if(set.find(num - 1) == set.end())
            {
                int tmp = 1;
                int curNum = num + 1;
                while(set.find(curNum) != set.end())
                {
                    ++curNum;
                    ++tmp;
                }
                ret = max(ret, tmp);
            }
            
        }
        return ret;
    }
};

用哈希记录每个值，然后找，而且仅仅从连续子串的开头开始，跳过所有的中间量

明明是O(n)为啥比第一个O(nlogn)还慢

discussion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> map;
        int r = 0;
        for(auto& num : nums)
        {
            if(!map[num]) // 仅仅对于没建立过路径的数字来建立，因为如果重复建立，会导致结果重复累加
            // 这里的num如果是中间的点的话，更新他不会有什么影响，因为这表示他周围的点已经计算完他们本身为起点或终点的最大长度了，不会重复计算
            // 如果是端点，那也可以更新，总之就是让他不为0。
            // 事实上，这里的map[num]赋值仅仅是为了标记他已经走过，赋任何值都可以
                r = max(r, map[num] = map[num + map[num + 1]] = map[num - map[num - 1]] = map[num - 1] + map[num + 1] + 1); 
        }
        return r;
    }
};

对于n，几种情况

  1. 有一条到n-1的路径，则总长度为len(n-1)+1
  2. 有一条n+1到后面的路径，则总长度为len(n+1)+1
  3. 都没有，则长度为1

对于一条路径来说，比如123456，则对于这条路径的开头和结尾来说，他们的最长长度应该是一样的，给他们赋予同样的值，中间的点会走到，然后会更新值，走过的点就不走了

差不多就是每走到一个点，如果他周围还没有，那就建立一条小路，后面走到中间的后，自然会连接两条小路

对于每个点来说，他都记录以他为起点或者终点的最长路的长度，如果走到的这个点没走到过，那就说明他前面的那条路没有经过现在，必然是反向，于是这个点连接前后，更新始终的值。就仿佛2个水珠的中间滴入一滴水，三者融为一体。

1624605638438.png

Posted on Edited on In Disqus:
Symbols count in article: 1.6k Reading time ≈ 1 mins.

72. Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
        for(int i = 1; i <= word1.size(); ++i)
            dp[i][0] = i;
        for(int i = 1; i <= word2.size(); ++i)
            dp[0][i] = i;
        
        for(int i = 1; i <= word1.size(); ++i)
        {
            for(int j = 1; j <= word2.size(); ++j)
            {
                if(word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else 
                    dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;
            }
        }
        return dp.back().back();
    }
};

T(n) : O(n^2)
S(n) : O(n^2)

动态规划

设dp[i][j]代表从word1[0...i)转到word2[0...j)所需的最小次数。假设已知dp[i - 1][j - 1]，即word1[0...i - 1)转到word2[0...j - 1)所需的最小步数，此时可保证，将面临一些几种情况，此时可保证word1[0...i - 1) == word2[0...j - 1)。

  1. 当word1[i - 1] == word2[j - 1], 则dp[i][j] = dp[i - 1][j - 1]。
  2. 当word1[i - 1] != word2[j - 1], 则可以replace(word1[i - 1], word2[j - 1])，dp[i][j] = dp[i - 1][j - 1] + 1。
  3. 当word1[0...i - 1) == word2[0...j)，则可以delete(word1[i - 1])，dp[i][j] = dp[i - 1][j] + 1。
  4. 当word1[0...i - 1) + word2[j - 1] == word2[0...j)，则可以insert(word2[j - 1])，dp[i][j] = dp[i][j - 1] + 1。 对于后三种情况，需要获得最小的步数，因此取最小值即可忽略复杂的判断(考虑replace，insert，delete)三种操作

base:

  1. dp[i][0] = i，所有word[0...i)转到0长度都需要删掉i个数字
  2. dp[0][j] = j，同理
optimize space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<int> dp(word2.size() + 1, 0);
        for(int i = 1; i <= word2.size(); ++i)
            dp[i] = i;
        
        for(int i = 1; i <= word1.size(); ++i)
        {
            int prev = dp[0];
            dp[0] = i;
            for(int j = 1; j <= word2.size(); ++j)
            {
                auto tmp = dp[j];
                if(word1[i - 1] == word2[j - 1])
                    dp[j] = prev;
                else 
                    dp[j] = min(min(dp[j - 1], dp[j]), prev) + 1;
                prev = tmp;
            }
        }
        return dp.back();
    }
};

优化方式参考221. Maximal Square

注意这里需要每次更新dp[0]用做base

Posted on Edited on In Disqus:
Symbols count in article: 1.5k Reading time ≈ 1 mins.

98. Validate Binary Search Tree

中序遍历BST是元素从小到达排列的，因此如果未严格单调递增，就是无效的BST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* pre = nullptr;
        while(!s.empty() || root)
        {
            while(root)
            {
                s.push(root);
                root = root->left;
            }
            auto p = s.top();
            s.pop();
            if(pre && pre->val >= p->val)
                return false;
            pre = p;
            root = p->right;
        }
        return true;
    }
};
每个左点的上界为父节点，下界则沿用上一节点，右点的下界为父节点，上界则沿用上衣节点，这样可以保证界限是由上面传递下来的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MAX, LONG_MIN);
    }
private:
    bool helper(TreeNode* node, long max, long min)
    {
        if(!node)
            return true;
        if(node->val >= max || node->val <= min)
            return false;
        else
            return helper(node->left, node->val, min) && helper(node->right, max, node->val);
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 875 Reading time ≈ 1 mins.

295. Find Median from Data Stream295. Find Median from Data Stream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(even)
        {
            large.push(num);
            small.push(large.top());
            large.pop();
        }else
        {
            small.push(num);
            large.push(small.top());
            small.pop();
        }
        even = !even;     
    }
    
    double findMedian() {
        if(even)
            return static_cast<double>((small.top() + large.top())) / 2;
        else
            return small.top();
    }
private:
    priority_queue<int> small;
    priority_queue<int, vector<int>, std::greater<int>> large;
    bool even = true;
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

small存放小的一半，large存放大的一半，保证small的大小永远等于large.size()或large.size() + 1

Posted on Edited on In Disqus:
Symbols count in article: 4.2k Reading time ≈ 4 mins.

297. Serialize and Deserialize Binary Tree

瞎写，懒得看别人写法了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "[]";
        queue<TreeNode*> q;
        string res = "[";
        q.push(root);
        int nodeNum = 1;
        while(!q.empty() && nodeNum)
        {
            auto p = q.front();
            q.pop();
            if(p)
            {
                nodeNum += (p->left ? 1 : 0) + (p->right ? 1 : 0);
                q.push(p->left);
                q.push(p->right);
                --nodeNum;
                res += to_string(p->val);
            }else
                res += "null";
            res += ",";
        }
        res.back() = ']';
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<TreeNode *> q;
        auto nodes = parseString(data);
        TreeNode *root = nullptr;
        bool leftNotIn = true;
        for (const auto &node : nodes)
        {
            if (q.empty())
                q.push(root = new TreeNode(*node));
            else
            {
                auto curNode = q.front();
                if (!curNode->left && leftNotIn)
                {
                    if (node)
                        q.push(curNode->left = new TreeNode(*node));
                    else
                        curNode->left = nullptr;
                    leftNotIn = false;
                }
                else if (!curNode->right)
                {
                    if (node)
                        q.push(curNode->right = new TreeNode(*node));
                    else
                        curNode->right = nullptr;
                    q.pop();
                    leftNotIn = true;
                }
            }
        }
        return root;
    }
private:
    bool isDigitalOrCharacter(const char &ch)
    {
        return ('0' <= ch && '9' >= ch) || ('a' <= ch && 'z' >= ch) || ch == '-';
    }

    bool isSplitCondition(const char &ch)
    {
        return ch == ',' || ch == ']';
    }
    std::vector<std::shared_ptr<int>> parseString(std::string &s)
    {
        std::queue<char> cache;
        std::vector<std::shared_ptr<int>> res;
        auto begin = s.begin();
        auto end = s.end() - 1;
        while (*begin != '[')
            ++begin;
        while (*end != ']')
            --end;
        ++begin;
        for (; begin != end + 1; ++begin)
        {
            if (isSplitCondition(*begin))
            {
                int realNum = 0;
                int positive = 1;
                if (cache.empty())
                    return {};
                if (cache.front() == '-')
                {
                    positive = -1;
                    cache.pop();
                }
                while (!cache.empty())
                {
                    realNum = realNum * 10 + static_cast<int>(cache.front() - '0');
                    cache.pop();
                }
                if (realNum == 69560) // null
                    res.push_back(nullptr);
                else
                    res.push_back(std::make_shared<int>(realNum * positive));
            }
            else if (isDigitalOrCharacter(*begin))
            {
                cache.push(*begin);
            }
        }
        return res;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
1620118342754.png

r 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "";
        queue<TreeNode*> q;
        q.push(root);
        string ret;
        while(!q.empty()) {
            for(auto i = q.size(); i > 0; --i) {
                auto p = q.front();
                q.pop();
                if(!p)
                    ret += "n ";
                else {
                    ret += to_string(p->val) + " ";
                    q.push(p->left);
                    q.push(p->right);
                }
            }
        }
        ret.pop_back();
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())
            return nullptr;
        stringstream ss(data);
        string cur;
        getline(ss, cur, ' ');
        auto root = new TreeNode(stoi(cur));
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            for(auto i = q.size(); i > 0; --i) {
                auto p = q.front();
                q.pop();
                getline(ss, cur, ' ');
                if(cur[0] != 'n') {
                    p->left = new TreeNode(stoi(cur));
                    q.push(p->left);
                }
                getline(ss, cur, ' ');
                if(cur[0] != 'n') {
                    p->right = new TreeNode(stoi(cur));
                    q.push(p->right);
                }
            }
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

Posted on Edited on In Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

31. Next Permutation

题目意思解释: 比如有[9, 5, 6, 4, 1],代表一个数95641，要找到通过数列中数字组合而成的大于这个数中的最小一个，即96145, [9, 6, 1, 4, 5]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int turningPoint = 0;
        int justGreater = 0;
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] > nums[i - 1])
            {
                turningPoint = i;
                justGreater = i;
            }else if(turningPoint && nums[i] > nums[turningPoint - 1])
                justGreater = i;       
        }
        if(turningPoint)
            swap(nums[justGreater], nums[turningPoint - 1]);
        reverse(nums, turningPoint);
    }
private:
    void reverse(vector<int>& nums, int start)
    {
        int end = nums.size() - 1;
        while(start < end)
            swap(nums[start++], nums[end--]);
    }
};

要注意到转折点后的序列必然是递减的

寻找序列中第一个满足a[i] > a[i - 1]且其后序列递减的一部分作为转折点，将a[i - 1]和后面递减序列中刚刚好大于a[i - 1]的数a[j]交换，因为a[j - 1] > a[j]其a[j + 1] < a[j]，而a[i - 1] < a[j] && a[i - 1] > a[j + 1]，所以交换后后面的递减次序不变，为了实现最小，只需要将交换后的后面再升序排列即可。

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int turningPoint = -1;
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] > nums[i - 1])
                turningPoint = i;
        }
        if(turningPoint == -1)
        {
            sort(nums.begin(), nums.end());
        }else
        {
            sort(nums.begin() + turningPoint, nums.end());
            auto num = upper_bound(nums.begin() + turningPoint, nums.end(), nums[turningPoint - 1]);
            swap(*num, nums[turningPoint - 1]);
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3.1k Reading time ≈ 3 mins.

42. Trapping Rain Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty())
            return 0;
        vector<int> leftWater(height.size() + 1);
        int maxNum = 0;
        int maxIndex = 0;
        for(int i = 0; i < height.size(); ++i)
        {
            if(height[i] > maxNum)
            {
                maxIndex = i;
                maxNum = height[i];
            }
            leftWater[i + 1] = maxNum - height[i] + leftWater[i];
        }
        maxNum = 0;
        for(int i = height.size() - 1; i > maxIndex; --i)
        {
            if(height[i] > maxNum)
            {
                maxNum = height[i];
            }
            leftWater[maxIndex + 1] += maxNum - height[i];
        }
        return leftWater[maxIndex + 1];
    }
};

答案中的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty())
            return 0;
        vector<int> left(height.size());
        left[0] = height[0];
        vector<int> right(height.size());
        right[height.size() - 1] = height.back();
        for(int i = 1; i < height.size(); ++i)
            left[i] = max(left[i - 1], height[i]);
        for(int i = height.size() - 2; i >= 0; --i)
            right[i] = max(right[i + 1], height[i]);
        int ans = 0;
        for(int i = 0; i < height.size(); ++i)
            ans += min(left[i], right[i]) - height[i];
        return ans;
    }
};

借图 1620046011104.png 只可意会，左边由两边都是取得最低的量

使用stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty())
            return 0;
        stack<int> bars;
        int cur = 0;
        int res = 0;
        while(cur < height.size())
        {
            while(!bars.empty() && height[cur] > height[bars.top()])
            {
                auto top = bars.top();
                bars.pop();
                if(bars.empty())
                    break;
                int distance = cur - bars.top() - 1;
                int heightBounded = min(height[cur], height[bars.top()]) - height[top];
                res += distance * heightBounded;
            }
            bars.push(cur++);
        }
        return res;
    }
};

每碰到一个比之前的障碍高的就计算一次体积，每次计算的是方形，进行填充，由于比较低的在填完后被pop，而他的障碍会被push，因此在填充完毕后，对于后面来看，这就是一条水平线，示意图如下 1620108974861.png 图中红色标号表示填充水块的次序

Two Points
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int leftMax = 0;
        int rightMax = 0;
        int res = 0;
        while(left < right)
        {
            if(height[left] < height[right])
            {
                if(leftMax < height[left])
                    leftMax = height[left];
                res += leftMax - height[left];
                ++left;
            }else
            {
                if(rightMax < height[right])
                    rightMax = height[right];
                res += rightMax - height[right];
                --right;
            }
        }
        return res;
    }
};

中间盛的水可以由左右边界来决定，当左边比右边矮的时候，水由左边边界决定，因为条件决定了左边不会比右边高，所以左边的水量又会受左边的最高峰影响，左边最高峰之左，水由边界决定，最高峰之右，由最高峰决定。将其最高峰之左再细分，又会有许多局部最高峰，由此一来，对于每一步更新其最高峰，更新最高峰之前的水由前一个局部边界决定，更新最高峰后的水由最高峰决定，同时这个局部最高峰又成了下一个区域的边界。

复习
dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> memo(n);
        int before = 0;
        for(int i = 0; i < n; ++i)
            memo[i] = before = max(before, height[i]);
        int ret = 0;
        int right = 0;
        for(int i = n - 1; i >= 0; --i)
        {
            right = max(height[i], right);
            ret += min(memo[i], right) - height[i];
        }
        return ret;
    }
};
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = 0;
        int ret = 0;
        int i = 0, j = height.size() - 1;
        while(i < j)
        {
            left = max(left, height[i]);
            right = max(right, height[j]);
            if(left < right)
                ret += left - height[i++];
            else
                ret += right - height[j--];
        }
        return ret;
    }
};