周赛 – 194 – 避免洪水泛滥

3. 避免洪水泛滥

思路

很显然,在任意两个相等的 rains[i] 之间,必须需要一个 0 ,否则肯定会被淹没。而且对于每一个 0 ,我们一定是先抽干最紧急的湖泊,也就是最早第二次出现的湖泊。

所以,肯定先要处理出所有的相同数的相邻数对。比如说 2 号湖泊分别在位置 0, 3, 4, 7 出现过,那么需要处理出的数对有 (0, 3), (3, 4), (4, 7)。而我们在计算答案的时候,一定是顺次遍历rains数组并且记录答案。如果rains的该位不是 0 ,那么输出 -1 ,否则,我们一定是将第二位最小的数对拿来处理。处理的时候,需要判断一下当前这次抽干是否在数对两个数字之间,否则也无法抽干的,比如说当前已经遍历到第四位发现一个抽干机会,而需要处理的是 (0, 3),那么洪水已经来过了,一切都太晚了= =。

所以,首先我们需要处理出所有的数对。用一个map记录某个数字上次出现的位置(这个位置需要从 1 开始,因为未被访问的map默认是 0 ),那么遍历到某一个 now = rain[i] 的时候,如果 mp[now] != 0,说明可以组成新的数对,新的数对是 (mp[now] - 1, i),我们使用 nxt[mp[now] - 1, i) 来记录。

第二步也就是计算答案。在计算答案的时候,我们用一个优先队列来维护需要被处理的数对。当遍历到一个位置 i 时,分为两种情况:

  • rain[i] 不为 0 时。存在数对 (i, nxt[i]) 的时候,我们将其加入优先队列。使用优先队列的时候需要注意两点,一是因为pair的优先队列是对第一维排序的,而我们需要排序的是nxt[i],所以 pair.first = nxt[i], pair.second = i;第二点是我们需要从小到大排序,避免麻烦之间放入负数。
  • rain[i]0 时。处理优先队列队首,判断队首数对是否能被处理,如果可以就处理并记录答案,如果不可以说明这种情形必定洪水泛滥,返回空。

最后需要判断一下队列是否为空,不为空说明还有洪水没能被处理,返回空。

代码

const int MAXN = 1e5 + 5;

int nxt[MAXN];
map<int, int> pre;
priority_queue<pair<int, int>> que;

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        pre.clear();
        while(!que.empty()) que.pop();
        
        int n = rains.size();
        for(int i=0; i<n; i++) nxt[i] = -1;
        for(int i=0; i<n; i++) {
            int now = rains[i];
            if(now == 0) continue;
            if(pre[now]) nxt[pre[now] - 1] = i;    
            pre[now] = i + 1;
        }
        
        vector<int> ans(n, 0);
        for(int i=0; i<n; i++) {
            int now = rains[i];
            if(now != 0) {
                ans[i] = -1;
                if(nxt[i] != -1) que.push(make_pair(-nxt[i], -i));
            }
            else {
                if(que.empty()) {
                    ans[i] = 1;
                    continue;
                }
                pair<int, int> x = que.top(); que.pop();
                if(-x.second <= i && i <= -x.first) ans[i] = rains[-x.first];
                else return {};
            }
        }
        if(!que.empty()) return {};
        return ans;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇