发表更新LeetCode / 算法27 分钟读完 (大约4100个字)

LeetCode-单调栈

739. 每日温度

  • 简单，通过单调栈，弹出栈中小于当前元素的元素，可以找到弹出元素的第一个大于其的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> monoStk;
        int len = temperatures.size();
        vector<int> res(len);
        for(int i = 0; i < len; i++) {
            while(!monoStk.empty() && temperatures[monoStk.top()] < temperatures[i]) {
                int top = monoStk.top();
                res[top] = i - top;
                monoStk.pop();
            }
            monoStk.push(i);
        }
        return res;
    }
};

42. 接雨水

AC1

思路

  • 构造了一个这样的测试用例
1
2
3
4
vector<int> testcase = {3,2,1,0,1,2,1,0,1,3};
// |                 |
// | |       |       |
// | | | _ | | | _ | |
  • 如果构造一个递增的栈，那么栈顶元素比我大时，就要把他们全弹出，显然不合理
  • 构造一个递减的栈，从栈顶弹出小于当前长度的元素，那么被弹出的区间内能装水的最大量就是min(i, top) - height[j]
  • 这样虽然用了单调栈，但复杂度还是高

代码

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
class Solution {
public:
    int trap(vector<int>& height) {
        int len = height.size();
        stack<int> monoStk;
        vector<int> rain(len, 0);
        for(int i = 0; i < len; i++) {
            int top = len;
            while(!monoStk.empty() && height[monoStk.top()] < height[i]) {
                top = monoStk.top();
                monoStk.pop();
            }
            if(!monoStk.empty()) top = monoStk.top();
            for(int j = top; j < i; j++) {
                rain[j] = min(height[top], height[i]);
            }
            monoStk.push(i);
        }
        int rainSum = 0;
        for(int i = 0; i < len; i++) {
            if(rain[i] > height[i]) {
                rainSum += rain[i] - height[i];
            }
        }
        return rainSum;
    }
};

// |                 |
// | |       |       |
// | | | _ | | | _ | |

优化

  • 如何在弹栈过程中计算接水量呢
  • i把x弹出后，此时top（若存在）与i就是两个墙壁，取其最小值，减去被弹栈元素的高度，乘以宽度，就是两个墙壁之间的储水量
  • 如果有更高的两面墙将其包围，由于单调栈的性质，计算的是墙与被弹元素的差值，不会重复计算底部的雨水
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 trap(vector<int>& height) {
        int len = height.size();
        int rainSum = 0;
        stack<int> monoStk;
        for(int i = 0; i < len; i++) {
            int top = len;
            while(!monoStk.empty() && height[monoStk.top()] < height[i]) {
                top = monoStk.top();
                monoStk.pop();
                if (monoStk.empty()) {
                    break;
                }
                int left = monoStk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                rainSum += currWidth * currHeight;
            }
            monoStk.push(i);
        }
        return rainSum;
    }
};

456. 132 模式

思路

  • 已知这道题用单调栈，但是构造递增的栈还是递减栈呢，so hard to tell
  • 通过尝试，最后使用递减栈
  • 将小于当前元素的所有栈內元素弹出后，如果栈内还存在元素，则满足nums[k] < nums[j] (当前元素是nums[k])
  • 现在只要保证nums[j]左侧存在元素nums[i] < nums[k]，开一个数组保存当前最小值即可

ac代码

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:
    bool find132pattern(vector<int>& nums) {
        int len = nums.size();
        stack<int> monoStack;
        vector<int> minArr(len + 1, INT_MAX);
        for(int i = 1; i <= len; i++) {
            minArr[i] = min(minArr[i-1], nums[i-1]);
        }
        for(int i = 0; i < len; i++) {
            while(!monoStack.empty() && nums[monoStack.top()] <= nums[i]) {
                monoStack.pop();
            }
            if(!monoStack.empty()) {
                int top = monoStack.top();
                if(nums[i] > minArr[top]) {
                    return true;
                }
            }
            monoStack.push(i);
        }
        return false;
    }
};

581. 最短无序连续子数组

思路

  • 创建一个单调递增栈，当有元素被弹出时，说明后面的元素被放到前面了，当前元素下标和栈顶元素下标需要被排序
  • 由于题目要求一个最大的连续子数组，所以要求下标的最大范围
  • 对于特殊情况，即数组中有连续相等的数字时，需要判断这些元素是否也需要参与排序，即增大子数组的范围
  • 需要记录被弹出元素的最大值，如果小于它，则需要参与排序。

代码

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 findUnsortedSubarray(vector<int>& nums) {
        stack<int> monoStk;
        int len = nums.size(), l = len, r = -1;
        int maxPop = INT_MIN;
        for(int i = 0; i < len; i++) {
            while(!monoStk.empty() && nums[monoStk.top()] > nums[i]) {
                l = min(l, monoStk.top());
                r = i;
                maxPop = max(maxPop, nums[monoStk.top()]);
                monoStk.pop();
            }
            monoStk.push(i);
        }
        while(!monoStk.empty()) {
            if(nums[monoStk.top()] < maxPop) r = max(r, monoStk.top());
            monoStk.pop();
        }
        return max(r - l + 1, 0);
    }
};

654. 最大二叉树

笨蛋做法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int> nums) {
        if(nums.size() == 0) return nullptr;
        auto max_ite = max_element(nums.begin(), nums.end());
        TreeNode *node = new TreeNode(*max_ite);
        node->left = constructMaximumBinaryTree({nums.begin(), max_ite});
        node->right = constructMaximumBinaryTree({++max_ite, nums.end()});
        return node;
    }
};

笨蛋方法2

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
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int> nums) {
        int len = nums.size();
        auto cmp = [&nums](int i, int j) { return nums[i] < nums[j]; };
        priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
        for(int i = 0; i < len; i++) {
            q.push(i);
        }
        map<TreeNode*, int> m;
        TreeNode *root = nullptr;
        if(!q.empty()) {
            int top = q.top();
            root = new TreeNode(nums[top]);
            m[root] = top;
            q.pop();
        }
        while(!q.empty()) {
            int top = q.top();
            q.pop();
            TreeNode *node = root, *p = nullptr;
            while(node) {
                p = node;
                if(m[node] < top) {
                    node = node->right;
                } else {
                    node = node->left;
                }
            }
            if(p) {
                TreeNode *tmp = new TreeNode(nums[top]);
                m[tmp] = top;
                if(m[p] < top) {
                    p->right = tmp;
                } else {
                    p->left = tmp;
                }
            }
        }
        return root;
    }
};

单调栈

思路

testcase

[3,2,1,6,0,5]

  • 观察这个测试用例生成的二叉树
  • 如果构造一个递减的单调栈，在6进入前，从栈顶开始栈內元素依次为
    • [1,2,3]
  • 6入栈时，会将他们三个弹出，他们三个刚好依次为下一个的右子树
  • 6入栈后，被弹出的最后一个元素为6的左子树
  • 观察6的右子树，发现也满足这个规律
  • 尝试利用这个规律编码，果然对了！！哈哈，开心

代码

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:
    TreeNode* constructMaximumBinaryTree(vector<int> nums) {
        nums.push_back(INT_MAX);
        int len = nums.size();
        stack<int> monoStack;
        vector<TreeNode *> nodes(len);
        for(int i = 0; i < len; i++) {
            nodes[i] = new TreeNode(nums[i]);
        }
        for(int i = 0; i < len; i++) {
            int top = len;
            while(!monoStack.empty() && nums[monoStack.top()] < nums[i]) {
                top = monoStack.top();
                monoStack.pop();
                if(!monoStack.empty() && nums[monoStack.top()] < nums[i]) {
                    nodes[monoStack.top()]->right = nodes[top]; 
                }
            }
            if(top < len) nodes[i]->left = nodes[top];
            monoStack.push(i);
        }
        TreeNode *root = nodes.back();
        return root->left;
    }
};

769. 最多能完成排序的块

  • wow amazing！^v^
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int len = arr.size(), ret = 0;
        stack<int> monoStack;
        for(int i = 0; i < len; i++) {
            int top = !monoStack.empty() && monoStack.top() > arr[i] ? monoStack.top() : -1;
            while(!monoStack.empty() && monoStack.top() > arr[i]) {
                monoStack.pop();
            }
            if(top != -1) monoStack.push(top);
            else monoStack.push(arr[i]);
        }
        return monoStack.size();
    }
};

768. 最多能完成排序的块 II

  • yes, yes, yes, you no 看错，和上一题相同的代码
  • amazing! wow! ^v^#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int len = arr.size(), ret = 0;
        stack<int> monoStack;
        for(int i = 0; i < len; i++) {
            int top = !monoStack.empty() && monoStack.top() > arr[i] ? monoStack.top() : -1;
            while(!monoStack.empty() && monoStack.top() > arr[i]) {
                monoStack.pop();
            }
            if(top != -1) monoStack.push(top);
            else monoStack.push(arr[i]);
        }
        return monoStack.size();
    }
};

901. 股票价格跨度

  • 我太聪明啦，几分钟就写出来啦
  • 创建一个递减栈，将小于它的数全都弹出，此时与栈顶的距离就是span
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 StockSpanner {
    stack<pair<int, int>> monoStack;
    int day = 0;
public:
    StockSpanner() {
    }
    
    int next(int price) {
        day++;
        while(!monoStack.empty() && monoStack.top().second <= price) {
            monoStack.pop();
        }
        int span = day;
        if(!monoStack.empty()) {
            span = day - monoStack.top().first;
        }
        monoStack.emplace(day, price);
        return span;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

907. 子数组的最小值之和

单调栈

  • 我真聪明！！！！！
  • 用单调栈找到当前元素左右两侧第一个比他小的元素位置，分别记录到left[i], right[i]
  • 由元素arr[i]为最小值的子数组个数为
    • (right[i] - i + 1l) * (i - left[i] + 1l)
  • 由于构造的是递减栈，为了防止世界被破坏比被弹出元素更大的元素已经被弹出了，赋值时使用被弹出元素的left/right
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
class Solution {
    static constexpr int MOD = 1000000007;
public:
    int sumSubarrayMins(vector<int>& arr) {
        stack<int> monoStack;
        int len = arr.size();
        int res = 0;
        vector<int> left(len), right(len, len - 1);
        for(int i = 0; i < len; i++) {
            left[i] = right[i] = i;
            while(!monoStack.empty() && arr[monoStack.top()] >= arr[i]) {
                int top = monoStack.top();
                left[i] = left[top];
                monoStack.pop();
            }
            monoStack.push(i);
        }
        monoStack = move(stack<int>());
        for(int i = len - 1; i >= 0; i--) {
            while(!monoStack.empty() && arr[monoStack.top()] > arr[i]) {
                int top = monoStack.top();
                right[i] = right[top];
                monoStack.pop();
            }
            monoStack.push(i);
        }
        for(int i = 0; i < len; i++) {
            res = (res + (right[i] - i + 1l) * (i - left[i] + 1l) * arr[i]) % MOD;
        }
        return res;
    }
};

2865. 美丽塔 I

这道题与2866. 美丽塔 II相同，只是数据规模更小一点，当时用枚举山峰做的，这次用单调栈

思路

  • 根据提示，每一个位置都有可能是山峰（其实只有局部最大值有可能），那么假设i为山峰时，要计算出总和，需要三个数据：
    • i左侧上升的最大和
    • i右侧下降（反过来看也是上升）的最大和
    • i的最大值
    • 将以上三个值相加，就是最终结果
  • 所以需要两个数据，存放所有i对应的左侧山坡最大和，右侧山峰最大和
  • 使用单调栈的思想，创建一个递增栈，当栈顶元素大于当前元素时，弹出其中元素
  • 将数组想想成一座座山峰
    • 如果当前元素没有弹出栈中元素，说明当前处于上升阶段，那么其左侧/右侧的最大和就可以是左侧/右侧的元素的值
    • 如果弹出了元素，且栈被弹空了，说明当前元素是从左/右开始到当前最小的元素，那么到目前为止的所有元素都只能取最小值
    • 如果弹出了元素，且栈没有被弹空，当前栈顶元素就是当前元素与其之间能建造的最大值，都取该栈顶元素建造塔，就能满足这个区间内的和最大，而且由于是递增栈，取栈顶元素为这个区间的值也不会破坏山脉的递增/递减性质，那么这个区间的和加上栈顶元素的高度和栈顶元素之和的最大和，就是到当前元素的最大和

代码

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
class Solution {
    int monoStack[1000 + 1];
    int stackPtr;
    void initStack() {
        stackPtr = 0;
    }
    int pop() {
        return monoStack[--stackPtr];
    }
    int top() {
        return monoStack[stackPtr - 1];
    }
    void push(int val) {
        monoStack[stackPtr++] = val;
    }
    bool empty() {
        return stackPtr == 0;
    }
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        int len = maxHeights.size();
        long long ans = INT_MIN;
        vector<long long> leftHill(len), rightHill(len);
        initStack();
        for(int i = 0; i < len; i++) {
            int topVal = len;
            while(!empty() && maxHeights[top()] > maxHeights[i]) {
                topVal = pop();
            }
            if(empty()) leftHill[i] = (i + 0ll) * maxHeights[i] + leftHill[0];
            else if(topVal  < len) leftHill[i] = (i - top() - 1ll) * maxHeights[i] + maxHeights[top()] + leftHill[top()];
            else if(i > 0) leftHill[i] = leftHill[i-1] + maxHeights[i-1];
            push(i);
        }
        initStack();
        for(int i = len - 1; i >= 0; i--) {
            int topVal = len;
            while(!empty() && maxHeights[top()] > maxHeights[i]) {
                topVal = pop();
            }
            if(empty()) rightHill[i] = (len - 1ll - i) * maxHeights[i] + rightHill[len - 1];
            else if(topVal  < len) rightHill[i] = (top() - i - 1ll) * maxHeights[i] + maxHeights[top()] + rightHill[top()];
            else if(i < len - 1) rightHill[i] = rightHill[i+1] + maxHeights[i+1];
            push(i);
            ans = max(ans, leftHill[i] + rightHill[i] + maxHeights[i]);
        }
        return ans;
    }
};

496. 下一个更大元素 I

  • emm，其实就是找nums2中每个元素右侧第一个比它大的元素，只是要映射到nums1中
  • 需求真的很绕，看清这一点这题就很简单，用一个map映射元素到nums1中的下标即可
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:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> m;
        int len1 = nums1.size(), len2 = nums2.size();
        vector<int> monoStack(len2), ret(len1, -1);
        int stackPtr = 0;
        for(int i = 0; i < len1; i++) {
            m[nums1[i]] = i;
        }
        for(int i = 0; i < len2; i++) {
            while(stackPtr > 0 && nums2[monoStack[stackPtr - 1]] < nums2[i]) {
                int top = monoStack[stackPtr - 1];
                if(m.count(nums2[top])) {
                    int index = m[nums2[top]];
                    ret[index] = nums2[i];
                }
                stackPtr--;
            }
            monoStack[stackPtr++] = i;
        }
        return ret;
    }
};

503. 下一个更大元素 II

这个比上一题更简单了？只是多一个需要循环比较而已
根据以前的经验，需要循环寻找的一般可以将数组扩大一倍，并复制一份

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:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        vector<int> monoStack(2*len), ret(len, -1);
        nums.resize(2*len);
        for(int i = 0; i < len; i++) {
            nums[i+len] = nums[i];
        }
        int stackPtr = 0;
        for(int i = 0; i < 2*len; i++) {
            while(stackPtr > 0 && nums[monoStack[stackPtr - 1]] < nums[i]) {
                int top = monoStack[stackPtr - 1];
                if(top >= len) top -= len;
                ret[top] = nums[i];
                stackPtr--;
            }
            monoStack[stackPtr++] = i;
        }
        return ret;
    }
};

1019. 链表中的下一个更大节点

  • 没意思，链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        stack<pair<int, int>> monoStack;
        vector<int> res;
        int index = 0;
        while(head) {
            res.push_back(0);
            while(!monoStack.empty() && monoStack.top().first < head->val) {
                res[monoStack.top().second] = head->val;
                monoStack.pop();
            }
            monoStack.emplace(head->val, index);
            index++;
            head = head->next;
        }
        return res;
    }
};

2454. 下一个更大元素 IV

单调栈+小顶堆

  • 构造单调递减栈，当一个数被弹栈时，说明遇到了比他大的第一个数，此时被弹出元素放入一个小顶堆中
  • 每个元素入栈前，先查看小顶堆中有没有比自己小的元素，如果有，则第二个比他大的数就找到了
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:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int len = nums.size();
        vector<int> res(len, -1);
        stack<int> monoStack;
        auto cmp = [&nums](int i, int j) { return nums[i] > nums[j]; };
        priority_queue<int, vector<int>, decltype(cmp)> monoQueue(cmp);
        for(int i = 0; i < len; i++) {
            while(!monoQueue.empty() && nums[monoQueue.top()] < nums[i]) {
                int top1 = monoQueue.top();
                monoQueue.pop();
                res[top1] = nums[i];
            }
            while(!monoStack.empty() && nums[monoStack.top()] < nums[i]) {
                int top = monoStack.top();
                monoStack.pop();
                monoQueue.push(top);
            }
            monoStack.push(i);
        }
        return res;
    }
};

单调栈+栈

  • 其实不必用小顶堆，被弹出的元素反序插入另一个栈即可
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
int init_io = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    return 0;
}();

class Solution {
    class Stack { // 用数组，快一点
        int stack[100000 + 1] = {0};
        int stackPtr = 0;
        public:
        Stack() { }
        Stack(size_t len, int val) { 
            if(len > 0) fill(stack, stack + len, val); 
        }
        void clear() { stackPtr = 0; }
        bool empty() { return stackPtr == 0; }
        int top() { return stack[stackPtr - 1]; }
        int pop() { return stack[--stackPtr]; }
        void push(int val) { stack[stackPtr++] = val; }
        int ptr() { return stackPtr; }
        int get(int index) { return stack[index]; }
    };
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        int len = nums.size();
        vector<int> res(len, -1);
        Stack monoStack;
        Stack seen;
        for(int i = 0; i < len; i++) {
            while(!seen.empty() && nums[seen.top()] < nums[i])
                res[seen.pop()] = nums[i];
            int ptr = monoStack.ptr();
            while(!monoStack.empty() && nums[monoStack.top()] < nums[i])
                monoStack.pop();
            for(int j = monoStack.ptr(); j < ptr; j++)
                seen.push(monoStack.get(j));
            monoStack.push(i);
        }
        return res;
    }
};

85. 最大矩形

转化为单调栈问题

  • 直接在图内搜索矩形的复杂度是m*m*n*n
  • 可以计算每个点(i, j)的右侧有几个连续的1
  • 对于某一列，右侧分别有[2,3,1]个连续的1，那么可能的矩形为2, 3, 1, 2+2, 1+1+1
    1. 构建一个递增栈，弹出所有大于当前元素的值后，以当前元素为高度的矩形就确定了
    1. 每个点入栈后，栈內元素是递增的，计算两两之间形成的矩形面积
  • 复杂度O(n*m*m)

思路1

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 Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> left1Cnt(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++) {
            left1Cnt[i][n - 1] = matrix[i][n - 1] - '0';
            for(int j = n - 2; j >= 0; j--) {
                if(matrix[i][j] == '1') left1Cnt[i][j] = 1 + left1Cnt[i][j+1];
            }
        }
        int ret = INT_MIN;
        for(int j = 0; j < n; j++) {
            vector<int> monoStack(m);
            vector<int> left(m, 0);
            int stackPtr = 0;
            int minCnt = INT_MAX;
            for(int i = 0; i < m; i++) {
                int top = -1;
                left[i] = i;
                minCnt = min(minCnt, left1Cnt[i][j]);
                ret = max(ret, (i + 1) * minCnt);
                while(stackPtr != 0 && left1Cnt[monoStack[stackPtr - 1]][j] > left1Cnt[i][j]) {
                    top = monoStack[stackPtr - 1];
                    stackPtr--;
                }

                if(top != -1) {
                    ret = max(ret, (i - left[top] + 1) * left1Cnt[i][j]);
                    left[i] = left[top];
                }
                monoStack[stackPtr++] = i;
                for(int ptr = 0; ptr < stackPtr; ptr++) {
                    ret = max(ret, (i - left[monoStack[ptr]] + 1) * left1Cnt[monoStack[ptr]][j]);
                }
            }
        }
        return ret;
    }
};

思路2

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
class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> left1Cnt(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++) {
            left1Cnt[i][n - 1] = matrix[i][n - 1] - '0';
            for(int j = n - 2; j >= 0; j--) {
                if(matrix[i][j] == '1') left1Cnt[i][j] = 1 + left1Cnt[i][j+1];
            }
        }
        int ret = INT_MIN;
        for(int j = 0; j < n; j++) {
            vector<int> monoStack(m);
            vector<int> left(m, 0), right(m, 0);
            int stackPtr = 0;
            for(int i = 0; i < m; i++) {
                int top = -1;
                while(stackPtr != 0 && left1Cnt[monoStack[stackPtr - 1]][j] >= left1Cnt[i][j]) {
                    top = monoStack[--stackPtr];
                }
                if(stackPtr == 0) left[i] = i;
                else {
                    top = monoStack[stackPtr - 1];
                    left[i] = i - top - 1;
                }
                monoStack[stackPtr++] = i;
            }
            stackPtr = 0;
            for(int i = m-1; i >= 0; i--) {
                int top = -1;
                while(stackPtr != 0 && left1Cnt[monoStack[stackPtr - 1]][j] >= left1Cnt[i][j]) {
                    top = monoStack[--stackPtr];
                }
                if(stackPtr == 0) right[i] = m-1 - i;
                else  {
                    top = monoStack[stackPtr - 1];
                    right[i] = top - i - 1;
                }
                monoStack[stackPtr++] = i;
            }
            for(int i = 0; i < m; i++) {
                ret = max(ret, (left[i] + right[i] + 1) * left1Cnt[i][j]);
            }
        }
        return ret;
    }
};

1504. 统计全 1 子矩形

笨蛋栈(两次单调栈)

  • 参考907. 子数组的最小值之和，找到每个节点作为最小值的左右两侧区间长度
  • 以当前元素i为最小值区间范围为[l, r]，则正方形个数是
    • (r - i + 1) * (i - l + 1) * mat[i][j]
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 numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int ret = 0;
        for(int i = 0; i < m; i++) {
            for(int j = n - 2; j >= 0; j--) {
                if(mat[i][j]) mat[i][j] = mat[i][j+1] + mat[i][j];
            }
        }
        vector<int> monoStack(m);
        vector<int> left(m), right(m);
        int stackTop = 0;
        for(int j = 0; j < n; j++) {
            stackTop = 0;
            for(int i = 0; i < m; i++) {
                int top = m;
                while(stackTop != 0 
                    && mat[monoStack[stackTop - 1]][j] >= mat[i][j]) {
                    top = monoStack[--stackTop];
                }
                if(top < m) left[i] = left[top];
                else if(stackTop != 0) left[i] = i;
                else left[i] = 0;
                monoStack[stackTop++] = i;
            }
            stackTop = 0;
            for(int i = m - 1; i >= 0; i--) {
                int top = m;
                while(stackTop != 0 
                    && mat[monoStack[stackTop - 1]][j] > mat[i][j]) {
                    top = monoStack[--stackTop];
                }
                if(top < m) right[i] = right[top];
                else if(stackTop != 0) right[i] = i;
                else right[i] = m-1;
                monoStack[stackTop++] = i;
                ret += ((right[i] - i + 1) * (i - left[i] + 1)) * mat[i][j];
            }
        }
        return ret;
    }
};

聪明栈(一次单调栈)

  • 题解，看不懂

LeetCode-单调栈

https://jingtianer.github.io/home/2023/12/22/LeetCode/LeetCode-刷题总结位单调栈/

作者

Meow Meow Liu

发布于

2023-12-22

更新于

2024-04-23

许可协议

#

评论

×