LeetCode 2024-03

解题记录

3 月总结

本月有价值的题目：

2024-03-01

2369 检查数组是否存在有效划分

给一个数组，做划分，如果存在划分，使得每个子数组都能满足以下之一：

1. 子数组恰由 2 个相等元素组成，例如，子数组 [2,2] 。
2. 子数组恰由 3 个相等元素组成，例如，子数组 [4,4,4] 。
3. 子数组恰由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求

则称为有效划分

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 106

一开始想错了，以为是集合划分，即元素位置可自由移动，然后就开始想暴搜

元素位置是固定的，采用动态规划

f[n] 表示前 n 个元素可以有效划分，f[i] 取决于 f[i-2] 和 f[i-3]

核心代码：

for(int i = 3; i <= n; i++) {
    f[i] = (f[i-2] && check2(nums[i-2], nums[i-1])) || (f[i-3] && check3(nums[i-3], nums[i-2], nums[i-1]));
}

今天的每日一题比较简单，只要审好题。

1 月份做的一道题目还是挺值得记录一下的（为什么放在了 3 月份的日志里呢，是因为 1 月份就刷了那一道题，不好意思水一篇 Blog）

2865 2865. 美丽塔 I

给定限高，要求最后形成一个山峰形状的数组，求最大高度和

数据范围不大，直接暴力枚举山峰点能通过，时间复杂度为 $O(n^2)$

但是通过使用两个单调栈+前缀和+后缀和，可以将时间复杂度降到 $O(n)$

long long maximumSumOfHeights(vector<int>& maxHeights) {
    vector<int> left;
    vector<int> right;
    vector<long long> preSum(maxHeights.size());
    vector<long long> sufSum(maxHeights.size());
    long long ans = 0;
    for(long long i = 0; i < maxHeights.size(); i++) {
        while(!left.empty() && maxHeights[left.back()] > maxHeights[i]) {
            left.pop_back();
        }
        if(left.empty()) {
            preSum[i] = (i + 1) * maxHeights[i];
        }
        else {
            preSum[i] = preSum[left.back()] + (i - left.back()) * maxHeights[i];
        }
        left.push_back(i);  
    }
    for(long long i = maxHeights.size() - 1; i >= 0; i--) {
        while(!right.empty() && maxHeights[right.back()] > maxHeights[i]) {
            right.pop_back();
        }
        if(right.empty()) {
            sufSum[i] = (maxHeights.size() - i) * maxHeights[i];
        }
        else {
            sufSum[i] = sufSum[right.back()] + (right.back() - i) * maxHeights[i];
        }
        right.push_back(i);  
        if (i == maxHeights.size() - 1) ans = max(ans, preSum[i]);
        else if (i == 0) ans = max(ans, sufSum[i]);
        else ans = max(ans, preSum[i] + sufSum[i] - maxHeights[i]);
    }
    return ans;
}

其实也就是单调栈的应用（Leetcode 是真喜欢出单调栈的题啊）

不过有一个细节需要注意，声明单调栈时，不能：

vector<int> left(maxHeights.size());

单调栈一开始需要为空，上述声明会用 0 填充，并且 size 不为 0.

2024-03-02

2368 受限条件下可到达节点的数目

比较简单的 DFS，只是需要预处理边和受限节点。看了题解，也可以用并查集解决。

2024-03-03

225 用队列实现栈

如题，要求用队列实现栈，只能使用队列的 push to back、pop from front, size, is empty

核心思想就是：最后插入队列的元素，排在队首

所以只需要特殊处理 push 操作，假设原本的队列已经满足上述要求，新插入的元素也能排到原本队列的队首，那么就可以模拟栈，栈的 pop、top 都直接操作队首元素。

push 操作可以使用辅助队列（即总共用两个队列），也可以只使用原队列（总共用一个队列）：

void push(int x) {
    q2.push(x);
    while (!q1.empty()) {
        q2.push(q1.front());
        q1.pop();
    }
    swap(q1, q2);
}

void push(int x) {
    int n = q1.size();
    q1.push(x);
    for (int i = 0; i < n; i++) {
        q1.push(q1.front());
        q1.pop();
    }
}

那么，模拟出来的栈，操作的时间复杂度，push 是 O(n)，pop、top、empty 均为 $O(1)$