左神算法进阶班3_4网易题——烽火传递

Bertha 。 2022-10-02 15:55 129阅读 0赞

**【题目】**  
一个数组中的数字组成环形山，数值为山高  
1 2 4 5 3  
规则，烽火传递：  
相邻之间的两座山必能看到烽火，  
非相邻的山之间有一边的山高都 <= 这两个非相邻山的山高，则这两座山能相互看到烽火。  
比如，1和4就不能看到，因为顺时针边，2比1大，挡住了，逆时针边，3和5都比1大，挡住了。  
而3与4就能看到，虽然逆时针边5挡住了，但顺时针边1和2没挡住3。  
问哪两座山能相互看到烽火；要求时间复杂为O(1)  
此题答案为(1, 2)(1, 3)(2, 4)(4, 5)(5, 3)(2, 3)(4, 3)  
  
**【题解】**  
【数组中的数字互不相同】  
在最高山N, 和次高山M，之间的任何一座山向顺时针，逆时针寻找，  
都有可以看到山N、M两座山，即有(n - 2) \* 2对，然后再加上N, M这两座山能相互看到  
故共有(n - 2) \* 2 + 1 = 2 \* n - 3对  
结论：n个不相同的数，共有(2 \* n - 3)对

**【数组中含有相同的数字】**  
单调栈：从大到小排序  
从任意一个最大值开始，以一个方向旋转，进行入栈操作  
当一个数被弹出栈时，他找到了2个可以相互看到山，即，将入栈的和他下面的  
当将入栈数与栈顶相等，则将两个数的信息共同记录在同一个栈位置，  
当弹出某个数为n条记录时，即在同一个位置记录了n次某个数，比如，有连续n个4入栈，则在相同位置记录n次4  
此时它弹出时，能看到的山为：Cn2 + n \* 2次其中Cn2\[n个4之间相互组合\] + n \* 2\[n个4与他两边的高山组合\]，  
当将遍历完数组后，栈中剩余的数弹出时：  
对于倒数第i > 2个剩余数弹出时，他能看到的山为：Cn2 + n \* 2  
对于倒数第二个剩余数弹出时，  
若最后一个数为 > 1个记录他能看到的山为：Cn2 + n \* 2  
若最后一个数为 == 1个记录他能看到的山为：Cn2 + n \* 1, 因为这是一个环。  
对于倒数第1个剩余数弹出时，他能看到的山为：Cn2

** 【代码】**

**　　**

1 #pragma once
     2 #include <iostream>
     3 #include <vector>
     4 #include <deque>
     5 
     6 
     7 using namespace std;
     8 
     9 int fireTranfer(vector<int>m)
    10 {
    11     //先找到最大值
    12     int res = 0;
    13     int maxIndex = 0;
    14     deque<pair<int, int>>d;//单调栈
    15     for (int i = 0; i < m.size(); ++i)//寻找最大值
    16         maxIndex = m[maxIndex] > m[i] ? maxIndex : i;
    17     d.push_back(make_pair(m[maxIndex], 1));
    18     for (int i = maxIndex + 1; i != maxIndex; ++i)
    19     {
    20         if (i == m.size())
    21         {
    22             i = -1;
    23             continue;
    24         }
    25 
    26         while (!d.empty() && m[i] > d.back().first)
    27         {
    28             int value, num;
    29             value = d.back().first;
    30             num = d.back().second;
    31             res += (num*(num - 1) / 2) + num * 2;//对于弹出数据进行计算组合
    32             d.pop_back();
    33         }
    34         if (m[i] == d.back().first)
    35             ++d.back().second;
    36         else
    37             d.push_back(make_pair(m[i], 1));//压入新数
    38 
    39 
    40     }
    41     //将队列中剩余的数据弹出来
    42     while (!d.empty())
    43     {
    44         int value, num;
    45         value = d.back().first;
    46         num = d.back().second;
    47         if (d.size() > 2)//不是最后两个数据
    48             res += (num*(num - 1) / 2) + num * 2;
    49         else if (d.size() == 2)//为倒数第二个数
    50             if (d.front().second > 1)
    51                 res += (num*(num - 1) / 2) + num * 2;
    52             else
    53                 res += (num*(num - 1) / 2) + num;
    54         else//为倒数第一个数
    55             res += (num*(num - 1) / 2);
    56         d.pop_back();
    57     }
    58     return res;
    59 }
    60 
    61 void Test()
    62 {
    63     vector<int>v;
    64     v = { 1,2,4,5,3 };
    65     cout << fireTranfer(v) << endl;
    66     v = { 2,5,3,4,3,4,5 };
    67     cout << fireTranfer(v) << endl;
    68     v = { 5,4,4,4 };
    69     cout << fireTranfer(v) << endl;
    70 
    71 }

转载于:https://www.cnblogs.com/zzw1024/p/11066599.html