admin 管理员组

文章数量: 1184232

烽火台问题(单调栈应用)

一、题目描述 

问题描述：给你一个数组，表示烽火台的信号值，烽火台是首尾相接的环形组成的，返回满足下列条件有多少对烽火台能两两通讯：1）相邻的烽火台能相互通讯2）不相邻的烽火台能相互通讯的条件为：两个烽火台经过的所有烽火台的信号值都不大于这两个中的最小那个。比如数组【1 2 4 3 5】相邻的【1 2】【2 3】【3 4】【4 5】【5 1】，不相邻的【5 4】可以通讯，
因为中间的3比4和5中小的要小，还有【5 2】也可以通讯，但是【3 2】【4 1】就不能相互通讯了。
所以一共返回7对

二、分析 

思路：使用单调栈实现，

1）遍历数组找到最大的元素压入栈底，后面入栈保证栈底到栈顶从大到小，栈中记录元素值和当前值出现的次数

2）如果遇到入栈元素比栈顶元素大，出栈结算，下面详细介绍结算的过程

3）如果遇到相同的元素则继续入栈，栈中元素出现的次数加1即可，比如下面这个例子

 

 4）现在看一种普遍的情况，总结出出栈结算的方式。

  5）如果没有出栈的情况或者遍历完了元素也没有出栈的情况

6）现在考虑只有最后两条记录的时候，有两种情况，分别是栈底元素出现次数≥2和小于2的情况，看图

总结：还没遍历完数组压栈和弹栈过程中,C(times,2)+times*2.
遍历完数组之后,弹栈时,相同元素内部还是有C(times,2)对,
如果栈底元素times大于等于2结算方式同上,为1则为C(times,2) + times*1,
因为times为1的时候顺时针和逆时针都和该元素成对,算一次即可

三、代码实现

#include<iostream>
#include<stack>
using namespace std;class Data {
public:int val;int times;Data(int num) :val(num), times(1) {}
};
long getInerNum(int n) {//如果n为1则返回0个，否则就是C(times,2),C(k,2)=k!/((k-2)!*2!) = k(k-1)/2return n == 1L ? 0L : (long)n*(long)(n - 1) / 2L;
}
long communication(int arr[], int arr_len) {if (arr == NULL || arr_len < 2) {//数组没有元素或者只有一个元素，返回0对return 0;}int max_index = 0;for (int i = 0; i < arr_len; ++i) {//在数组中找最大值的位置max_index = arr[max_index] > arr[i] ? max_index : i;}int value = arr[max_index];//爱的魔力转圈圈，如果到达最后一个则下一个从0开始，否则为max_index+1int next_index = max_index + 1 > arr_len - 1 ? 0 : max_index + 1;//从最大值位置的下一个开始遍历long res = 0L;stack<Data*> sta;sta.push(new Data(value));while (next_index!=max_index) {//如果next_index回到max_index表示我们遍历结束value = arr[next_index];while (value > sta.top()->val) {//这里采用最大值打底，所以栈不可能弹成空int times = sta.top()->times;res += (getInerNum(times) + times * 2);sta.pop();}//下面表示无法弹了，无法弹的原因有两个，小于或等于栈顶元素if (!sta.empty() && sta.top()->val == value)sta.top()->times++;elsesta.push(new Data(value));next_index = next_index+1 > arr_len - 1 ? 0: next_index + 1;//更新next_index}while (!sta.empty()) {int times = sta.top()->times;sta.pop();res += getInerNum(times);//如果不是倒数第二和倒数第一，则固定就是C(times,2)和times*2if (!sta.empty()) {res += times;if (sta.size() > 1) {//pop了之后还大于1表示栈中有3个以上元素，再加一次timesres += times;}else//否则只有2个元素，只有两个元素的时候考虑栈底元素的times是否大于，是则再加一次，否则不加res += sta.top()->times > 1 ? times : 0;}}return res;
}
int main() {int n;while (cin >> n) {int* arr = new int[n];for (int i = 0; i < n; ++i) {cin >> arr[i];}cout << communication(arr,n) << endl;}
}

本文标签： 烽火台问题(单调栈应用)

版权声明：本文标题：烽火台问题(单调栈应用) 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.roclinux.cn/b/1693763738a241432.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。