【5】417. 太平洋大西洋水流问题

思路

DFS/BFS，反向搜索，判断每个新位置是否能流到现在的位置。用矩阵记录是否能到达，使用位运算进行优化（1代表太平洋，2代表大西洋）。

代码

DFS

static vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
class Solution {
public:
    void dfs(int x, int y, int v, vector<vector<int>> &heights, vector<vector<int>> &waves){
        if(waves[x][y] & v) return;
        waves[x][y] |= v;

        int m = waves.size();
        int n = waves[0].size();

        for(const auto &d : dirs){
            int nx = x + d[0];
            int ny = y + d[1];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n && heights[nx][ny] >= heights[x][y])
            dfs(nx, ny, v, heights, waves);
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        const int M = heights.size();
        const int N = heights[0].size();
        // 流动记录矩阵
        vector<vector<int>> waves(M, vector<int>(N));

        for(int i = 0; i < M; i++){
            dfs(i, 0, 1, heights, waves);// 左边一列 太平洋
            dfs(i, N - 1, 2, heights, waves);// 右边一列 大西洋
        }
        for(int j = 0; j < N; j++){
            dfs(0, j, 1, heights, waves);// 上面一列 太平洋
            dfs(M - 1, j, 2, heights, waves);// 下面一列 大西洋
        }

        vector<vector<int>> ans;
        for(int i = 0; i < M; i++)
            for(int j = 0; j < N ; j++)
            if(waves[i][j] == 3)
                ans.push_back({i, j});
        return ans;
    }
};

// 简洁写法
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        const int m = heights.size();
        const int n = heights[0].size();
        vector<vector<int>> s(m, vector<int>(n));
        vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        auto dfs = [&](this auto&& dfs, int x, int y, int v) {
            if (s[x][y] & v) return;
            s[x][y] |= v;
            for (const auto& d : dirs) {
                int nx = x + d[0];
                int ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && heights[x][y] <= heights[nx][ny]) {
                    dfs(nx, ny, v);
                }
            }
        };

        for (int i = 0; i < m; ++i) {
            dfs(i, 0, 1);
            dfs(i, n - 1, 2);
        }
        for (int j = 0; j < n; ++j) {
            dfs(0, j, 1);
            dfs(m - 1, j, 2);
        }

        vector<vector<int>> ans;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (s[i][j] == 3) ans.push_back({i, j});
            }
        }
        return ans;
    }
};

BFS

懒得写了

【6】778. 水位上升的泳池中游泳

思路

注意：题目上游泳不需要时间，即可以瞬间移动（神人）。所以，在只要有一条能从0, 0通到N – 1, N – 1的路径存在的情况下，使等待时间t变得最小。

1.二分查找 + 遍历

二分查找相关题目：单调性分析 -> 区间搜索范围 -> 区间搜索方法
单调性分析：题目中提供等待的时间t，而t又跟可游泳的网格分布有关。t越大，可游泳的网格分布越大，满足条件的可能性越大；t越小，可游泳的网格分布越小，满足条件的可能性越小。
区间搜索范围：[0, N * N – 1]
区间搜索方法：当小于等于该数值时，如果路径存在，那么值一定小于等于该数值；如果路径不存在，那么值一定大于该数值。

2.并查集

模拟下雨，

3.Dijkstra

应用前提：1.正权 2.单源最短路径

代码

1.二分查找 + 遍历

static vector<vector<int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
class Solution {
public:
    bool dfs(vector<vector<int>> &grid, int x, int y, vector<vector<bool>>& visited, int th){
        if(x == grid.size() - 1 && y == grid.size() - 1) return true;
        for(const auto &d : dirs){
            int nx = x + d[0];
            int ny = y + d[1];
            if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && visited[nx][ny] == false && grid[nx][ny] <= th){
                visited[nx][ny] = true;
                if(dfs(grid, nx, ny, visited, th)) return true;
            }
        }
        return false;
    }
    int swimInWater(vector<vector<int>>& grid) {
        const int N = grid.size();
        int left = 0, right = N * N - 1;
        while(left < right){
            int mid = (left + right) >> 1;
            vector<vector<bool>>visited(N,vector<bool>(N,false));
            if(grid[0][0] <= mid&&dfs(grid, 0, 0, visited, mid)) right = mid;
            else{
                left = mid + 1;
            }
        }
        return left;
    }
};

【7】1488. 避免洪水泛滥

思路

下雨不可抽，不下雨可抽。导致洪水泛滥的原因是：前面湖泊已满，后面还要下雨。那么，我们是否可以看未来哪个湖泊最可能先引发洪水泛滥，进而考虑我们抽水的湖泊呢？
换句话说就是：延迟抽水，等到后面要发生洪水的时候，再决定之前抽水的湖泊

1.贪心 + 二分查找

使用有序集合st来存晴天的下标。在哈希表mp中，first存有水的湖泊，second存下标。有序集合 st 的排序方式是按照晴天日子的顺序排列的，这就确保了我们总是在最早的晴天日子中进行抽干操作，以最大程度地避免洪水的发生。

对于最后剩余的晴天，我们可以将它们用于抽干任意一个湖泊，为了方便，我们令其为 1。初始化时，我们将所有晴天的默认操作设为抽干湖泊1，这是一种“安全”的占位符。因为即使湖泊1是空的，抽干一个空的湖泊也不会产生负面影响（题目描述中抽干空湖泊是无事发生的）。

• 若 rains[i]=0，则将 i 加入有序集合 st。
• 若 rains[i]>0，表示第 rains[i] 湖泊将下雨，令 ans[i]=−1 表示这一天的湖泊不可抽干：
• 若第 rains[i] 是第一次下雨，则此时不会发生洪水。
• 否则我们需要在有序集合 st 中找到大于等于该湖泊上一次下雨天数的最小索引 idx（可以用二分查找实现），如果 idx 不存在（即没有晴天可以用于抽干），此时不能避免洪水的发生，按照题目要求返回一个空数组。否则我们令 ans[idx]=rains[i]，并在 st 中删除 idx，表示我们会在第 idx 天抽干 rains[i] 湖泊的水来避免第 i 天洪水的发生。

代码

1.贪心 + 二分查找

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        vector<int> ans(rains.size(), 1);
        set<int> st;
        unordered_map<int, int> mp;
        for (int i = 0; i < rains.size(); ++i) {
            if (rains[i] == 0) {
                st.insert(i);
            } else {
                ans[i] = -1;
                if (mp.count(rains[i])) {
                    auto it = st.lower_bound(mp[rains[i]]);
                    if (it == st.end()) {
                        return {};
                    }
                    ans[*it] = rains[i];
                    st.erase(it);
                }
                mp[rains[i]] = i;
            }
        }
        return ans;
    }
};

【8】2300. 咒语和药水的成功对数

思路

1.二分查找

公式：spells[i] * potions[j] >= success

spells[i]越大或potions[j]越大，成功概率越高。因为我们要咒语组合成功的药水数目，所以我们使用spells[i]来遍历数组。

逆推出：potions[j] >= success / spells[i]

可见，具有单调性，可以使用二分查找解决。

代码

1.二分查找

class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        sort(potions.begin(), potions.end());
        vector<int> res;
        for(auto & i : spells){
            // ​向上取整 ceil(a/b) = (a + b - 1) / b
            // 不小于 success / spells[i] 的最小整数，所以需要-1
            long long t = (success + i - 1)/ i - 1;
            // 取位置，算剩下potions的数量
            res.push_back(potions.size() - (upper_bound(potions.begin(), potions.end(), t) - potions.begin()));
        }
        return res;
    }
};

【9】3494. 酿造药水需要的最少总时间

思路

题目要求：每个药水都必须经过每个巫师处理，每个巫师同时间只能够处理一瓶药水，并且每个药水开始酿造后就无法停下。

注意：题目中每个药水要 必须 依次通过 所有 巫师处理

1.动态规划

从时刻0开始酿造药水，可以计算出后面的巫师结束酿造的时间。后面的巫师开始酿造的时间取决于前面的巫师结束酿造的时间，具有连续性，不能确定下来。所以，我们假设允许第 j 瓶药水的酿造过程不连续，前 j – 1 瓶仍连续。

公式推导：
设第 i 位巫师处理完第 j 瓶药水的时间是times[i][j]，那么有：

times[i][j]=max(times[i−1][j],times[i][j−1])+skill[i]×mana[j]

由于times[i−1][j]与旧纪录有关，times[i][j−1]与现记录有关，所以我们可以把times压缩成一维，记录旧值与新值。（一位数组滚动优化）

在经过每瓶药水递推后，由于之前假设允许第 j 瓶药水的酿造过程不连续产生了间隔，所以要反向遍历更新。

代码

1.动态规划

class Solution {
public:
    using LL = long long;
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();
        vector<LL> times(n);//降维

        for(int j = 0; j < m; j++){
            LL cur = 0;
            for(int i = 0; i < n; i++)
                cur = max(cur, times[i]) + skill[i] * mana[j]; 
            
            times[n - 1] = cur;
            for(int i = n - 2; i >= 0; i--)
                times[i] = times[i + 1] - skill[i + 1] * mana[j];
        }
        return times[n - 1];
    }
};

【10】3147. 从魔法师身上吸取的最大能量

思路

1.逆序遍历

从前往后看，数组是这样的：
[i]
[i, i + k]
[i, i + k, i + 2k]
[i, i + k, i + 2k, i + 3k]
[i, i + k, i + 2k, i + 3k, i + 4k]

从后往前看，
[i]
[i, i – k]
[i, i – k, i – 2k]
[i, i – k, i – 2k, i – 3k]
[i, i – k, i – 2k, i – 3k, i – 4k]

在这些个路径中，发现都是差为|k|的等差数列，即周期为k。于是，就i从0开始遍历到k-1。从题目中可以知道，最后要到达末尾，而起点是未知的，所以从末尾到起点逆着推比较好（就i从n-k开始遍历到n），这样也避免了一个问题（当energy数组中出现负数时，避免写多余代码修正数字）。

代码

1.逆序遍历

class Solution {
public:
    int maximumEnergy(vector<int>& energy, int k) {
        int n = energy.size(), ans = INT_MIN;
        //采用逆序是为了避免修正数字
        for(int i = n - k; i < n; i++){
            int sum = 0;
            for(int j = i;j >= 0; j -= k){
                sum += energy[j];
                ans = max(ans, sum);
            }
        }
        return ans;
    }
};

【11】3186. 施咒的最大总伤害

思路

1.动态规划

使用一个咒语power[i]后，就不能使用伤害绝对值相差1-2的咒语。所以，咒语的选择与power的顺序无关，与咒语伤害值有关。于是，可以先把一样伤害的咒语存到一起去。

设伤害为power_i 的咒语数量为count_i 。令f(i)表示从 0 到第 i 种咒语中选择，并且最后选择第 i 种咒语的最大总伤害。公式如下：

f(i) = f(j)_max(power_j < power_i – 2) + power_i * count_i

按伤害递增顺序遍历咒语，用单调指针维护f(j)_max ，即用于转移的最大值，最后答案为f中的最大值。

代码

1.动态规划

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        map<int, int> mp;
        for(int i: power){
            mp[i]++;
        }
        vector<pair<int, int>> p = {{-1e9, 0}};
        for(auto &i: mp){
            p.push_back(i);
        }
        int n = p.size();
        vector<long long> dp(n, 0);
        long long mx = 0;
        for(int i = 1, j = 1; i < n; i++){
            while(j < i && p[i].first - 2 > p[j].first){
                mx = max(mx, dp[j]);
                j++;
            }
            dp[i] = mx + 1LL * p[i].first * p[i].second;
        }
        long long ans = 0;
        for(int i = 0; i < n; i++)
            ans = max(ans, dp[i]);
        return ans;
    }
};