lcMovingWindow2 - 滑动窗口 2

Posted on Edited on

1 滑动窗口

priority_queue经常用 或者st、ed

2 例题：

1425constrainedSubsetSum 带限制最大子序列和

1 题目

https://leetcode.cn/problems/constrained-subsequence-sum/

2 解题思路

  • 1 解题思路:
    • 1.1 dp[i]表示以第i个数据结尾的带限制最大子序列和
    • 1.2 dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], …, dp[i-1])
    • 1.3 如何在i-1到i-k的数的集合中快速找到最大的满足限制要求的k？使用堆即可，只需要找到第一个满足要求的下标对应的值即可，不满足要求的下标可以pop掉（因为如果现在都无法满足要求，那么后面更加无法满足要求）
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
class Solution {
public:
    using pii = pair<int, int>;
   

    int constrainedSubsetSum(vector<int>& nums, int k) {
        // Let dp[i] be the solution for the prefix of the array that ends at index i,
        //     if the element at index i is in the subsequence.
        // dp[i] = nums[i] + max(0, dp[i-k], dp[i-k+1], ..., dp[i-1])

        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        int curRes = dp[0];
        
        // <idx, value>
        auto cmp = [](const pii& a, const pii& b) {
            return a.second < b.second;
        };
        priority_queue<pii, vector<pii>, decltype(cmp)> maxHeap(cmp);
         
        maxHeap.push({0, dp[0]});

        auto findInWindow = [](int minIdx, decltype(maxHeap)& window) {
            bool foundInWin = false;
            while(!window.empty()) {
                auto node = window.top();
                if(minIdx <= node.first) {
                    // window.pop();
                    return max(0, node.second);
                } else {
                    window.pop();
                }
            }
            return 0;
        };

        for(int i = 1; i < n; ++i) {
            dp[i] = nums[i] + findInWindow(max(0, i - k), maxHeap);
            curRes = max(curRes, dp[i]);
            // cout << i << "->    " << dp[i] << endl;
            maxHeap.push({i, dp[i]});
        }
        return curRes;
    }
}

1499findMaxOfEquationInVec 满足不等式的最大值

1 题目

https://leetcode.cn/problems/max-value-of-equation/

2 解题思路

  • 1 解题思路:
    • 1.1 首先能想到的是，对于数字point[i]的xy，我们可以维护一个window，其中放了所有xi,yi,满足|xi - x| <= k，然后我们遍历这个窗口的所有值，找到一个答案，但是这样复杂度是nk有点大了
    • 1.2 我们考虑一下，是不是需要考虑point[i]的左右距离为k的值？不需要，因为上面显然存在重复计算，比如x坐标为1,3,5的三个点，k = 100好了，对于1，考虑了3,5，对于3考虑了1，5，然而13的组合在x=1和这个点已经考虑过了，所以我们可以只考虑坐标的左半边或者右半边，我们以考虑左半边为例子
    • 1.3 由于是左半边，我们遍历的点称之为xj，那么xi就是左边的所有点，我们如何快速拿到结果呢？
      • res = for i < j && xj - xi <= k: max(yi + yj + |xi - xj|) = max(yj + xj + yi - xi)，去掉了绝对值
      • 然后可以看出来对于一个j，不就是求它左边窗口（窗口内的值需要满足：xj - xi <= k）中yi - xi的最大值吗？那不就是用priority_queue存起来就行了
      • 注意一点的是：当窗口中的xi, xj - xi > k可以放心pop，因为若当前的j都距离xi太远了，那后面的只会更加的遥远，于是可以pop 
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
class Solution {
public:
    
    using pii = pair<int, int>;
 
    static constexpr auto cmp = [](const pii& a, const pii& b) {
        return a.second < b.second;
    };

    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        // first: yi + yj + |xi - xj| == yj + xj + yi - xi
        // so: for each j, we shall found the biggest yi - xi and |xj - xi| <= k
        // using a priority_queue to store those yi - xi
        
        int n = points.size();
        // priority_queue<pii, vector<pii>, decltype(cmp)> maxHeapOri(cmp);
        priority_queue<pii, vector<pii>, decltype(cmp)> maxHeap(cmp);
        maxHeap.push({points[0][0], points[0][1] - points[0][0]}); // init it

        int curRes = INT_MIN;
        for(int j = 1; j < n; ++j) {
            // |xj - xi| <= k, we should consider xj - xi <= k or xi - xj <= k
            // but we can only consider those xj > xi, cause, when we try to consider xj < xi, 
            // the bigger J after j will be like xi, so all cases coverd
            int xj = points[j][0];
            int yj = points[j][1];
            // cout << "dealing: " << xj << " " << yj << endl;
            // auto maxHeap = maxHeapOri;
            while(1) {
                if(maxHeap.empty()) {
                    break;
                }

                auto t = maxHeap.top();
                int xi = t.first;
                int delatI = t.second;
                if(xi != xj ) {
                    if(xj - xi > k) {
                        // cout << "pop: " << xi << endl;
                        maxHeap.pop();
                    } else {
                        curRes = max(curRes, yj + xj + delatI);
                        break;
                    }    
                } else {
                    break;
                }
            }
            maxHeap.push({points[j][0], points[j][1] - points[j][0]});
        }
        return curRes;
        
    }
}

1610visiblePoints 可见顶点的最大数目

1 题目

https://leetcode.cn/problems/maximum-number-of-visible-points/

2 解题思路

  • 1 解题思路:
    • 1.1 算出极角，然后排序，然后用一个窗口，范围是angle，从最小移动到最大即可
    • 1.2 注意循环：比如-179和179这两个数字爱得很近，所以我们把排序好的点的极角加上360加入到点的数组中，滑动窗口就行
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
class Solution {
public:
    #define PI 3.14159265
 
    using Point = pair<pair<int, int>, double>;
    
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {

        vector<Point> calPoints;
        int n = points.size();
        int dupWithOriCnt = 0;
        // start form the negx: from -179.999 to 180
        auto calDegreeForPoints = [&](vector<int>& xy, vector<Point>& calPoints) {
            int x = xy[0] - location[0];
            int y = xy[1] - location[1];
            if(0 == x && 0 == y) {
                dupWithOriCnt += 1;
                return;
            }
            double result;
            result = atan2 (y, x) * 180 / PI;
            calPoints.emplace_back(Point{{x, y}, result});
        };   

        for(auto& p : points) {
            calDegreeForPoints(p, calPoints);
        }

        // all duplicated
        if(0 == calPoints.size()) {
            return dupWithOriCnt;
        }

        // sort by the angle
        sort(calPoints.begin(), calPoints.end(), [](const Point& a, const Point& b) {
            return a.second < b.second;
        });
        for(int i = 0; i < n; ++i) { // solve the circle problem
            auto p = calPoints[i];
            p.second += 360.0;
            calPoints.push_back(p);
        }

        // init window
        int st = 0;
        int ed = 0;

        double dAngle = angle;

        while(ed < calPoints.size() && calPoints[ed].second - calPoints[st].second <= dAngle) {
            ++ed;
        }
        --ed;
        int finRes = ed - st + 1;

        // mv window
        while(ed < calPoints.size()) {
            // mv st
            ++st;
            while(ed < calPoints.size() && calPoints[ed].second - calPoints[st].second <= dAngle) {
                ++ed;
            }
            if(ed == calPoints.size()) {
                finRes = max(finRes, static_cast<int>(calPoints.size()) - st);
            } else {
                --ed;
                finRes = max(finRes, ed - st + 1);
            }

        }

        return finRes + dupWithOriCnt;
    }
}

2302coountSunarrysScoreLessThanK 统计得分小于 K 的子数组数目

1 题目

https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/

2 解题思路

  • 1 解题思路:
    • 1.1 使用st，ed记录当前窗口，将窗口扩展至最大的满足分数小于k的条件
    • 1.2 ++st，找到下一个st
    • 1.3 对于每个窗口如何计数：
      • 计数：以st开始的区间
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 {
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        // alway keep st,ed as the max status:
        // score(st, ed) <= k, ed cannot be bigger for each st
        // then we statistic for each st, how many ways start with st

        // moving window score = getScore(nums[st:ed])
        long long st = 0; 
        long long ed = 0;
        long long n = nums.size();
        long long curScore = 0;
        long long cnt = 0;
        while(st < n) {
            bool edMoved = false;
            while(ed < n && (curScore + nums[ed])*(ed - st + 1) < k) {
                curScore += nums[ed];
                ++ed;
                edMoved = true;
            }

            // add cnt start with cur st
            if(curScore*(ed - st) < k) {
                cnt += ed - st;
            }
            
            curScore -= nums[st];
            ++st;
        }
        return cnt;
    }
};