今日头条笔试题:“最小数字*区间和”的最大值【单调栈】

题目描述:

  给定一段数组,求每个区间的最小值乘这段区间的和,输出每个区间得到的最大值。

  样例输入:[1 2 6],可能有以下几种情况:

  •   [1]:结果为1*1=1;
  •   [2]:结果为2*2=4;
  •   [6]:结果为6*6=36;
  •   [1,2]:结果为1*(1+2)=3;
  •   [2,6]:结果为2*(2+6)=16;
  •   [1,2,6]:结果为1*(1+2+6)=9;

  最大值为36,输出36即可。

解法:

  利用单调栈,从前向后和从后向前分别遍历一遍数组,得到每个元素的左边界和右边界(边界的定义即为碰到比该元素更小的即停止),最后用每个元素乘以每个元素对应的区间和,找出最大值即可。这里有一个技巧,为了防止每个元素重复计算一段区间和,可以提前开一个递增序列,用于保存某元素之前的各项和(含该元素),求取一段区间和的时候用右边界的递增和减去左边界减一的递增和即可。

复杂度:

  时间复杂度为O(n);

  空间复杂度为O(n);

代码(版本一:遍历两次分别得到左右边界):

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 struct Node{
 7     int val;
 8     int start;
 9     int end;
10 };
11 
12 int main()
13 {
14     std::ios::sync_with_stdio(false);
15     int n;
16     while(cin>>n){
17 
18         /********************************输入******************************/
19         vector<Node> v(n);
20         vector<long long> inc(n,0);//递增序列,方便计算一段区间的累加和
21         inc[-1]=0;//为了计算第一个数字的前序(应对v[i].start-1为-1的情况)
22         for(int i=0;i<n;++i){
23             cin>>v[i].val;
24             inc[i]= i==0 ? v[i].val : inc[i-1]+v[i].val;
25             v[i].start=i;
26             v[i].end=i;
27         }
28         /*******************处理得到每个元素的左边界(正向遍历)*****************/
29         stack<int> s;
30         int i=0;
31         while(i<(int)v.size()){
32             if(s.empty() || v[i].val > v[s.top()].val){
33                 s.push(i);
34                 ++i;
35             }
36             else{
37                 //插入的值更小的时候,将其start置为将要弹出的元素的start
38                 v[i].start=v[s.top()].start;
39                 s.pop();
40             }
41         }
42         /*******************处理得到每个元素的右边界(反向遍历)*****************/
43         while(!s.empty())//清空s,准备反向遍历
44             s.pop();
45         i=n-1;
46         while(i>=0){
47             if(s.empty() || v[i].val > v[s.top()].val){
48                 s.push(i);
49                 --i;
50             }
51             else{
52                 //插入的值更小的时候,将其start置为将要弹出的元素的start
53                 v[i].end=v[s.top()].end;
54                 s.pop();
55             }
56         }
57 //        for(int i=0;i<n;++i){
58 //            cout<<"("<<v[i].val<<","<<v[i].start<<","<<v[i].end<<")"<<endl;
59 //        }
60 //        for(int i=0;i<n;++i){
61 //            cout<<inc[i]<<endl;
62 //        }
63         /******************得到每个元素的结果,返回最大值即可*****************/
64         long long result=0;
65         int index_start=0,index_end=0;//得到最大值的区间(这里是从0开始计数的)
66         for(int i=0;i<n;++i){
67             long long cur_result=v[i].val*(inc[v[i].end]-inc[v[i].start-1]);
68             if(cur_result>result){
69                 result=cur_result;
70                 index_start=v[i].start;
71                 index_end=v[i].end;
72             }
73         }
74         cout<<result<<"\n";
75         cout<<index_start+1<<" "<<index_end+1<<"\n";//输出区间标记的时候从1开始计数,更直观
76     }
77     return 0;
78 }

代码(版本二:遍历一次即可得到左右边界):

 1 #include <iostream>
 2 #include <vector>
 3 #include <stack>
 4 using namespace std;
 5 
 6 struct Node{
 7     int val;
 8     int start;
 9     int end;
10 };
11 
12 int main()
13 {
14 //    std::ios::sync_with_stdio(false);
15     int n;
16     while(cin>>n){
17 
18         /********************************输入******************************/
19         vector<Node> v(n+1);
20         vector<long long> inc(n+1,0);//递增序列,方便计算一段区间的累加和
21         inc[-1]=0;//为了计算第一个数字的前序(应对v[i].start-1为-1的情况)
22         for(int i=0;i<n;++i){
23             cin>>v[i].val;
24             inc[i]= i==0 ? v[i].val : inc[i-1]+v[i].val;
25             v[i].start=i;
26             v[i].end=i;
27         }
28         v[n].val=0;//注意需要在末尾加入最小值,最终让栈中的元素全弹出来,更新计算
29         v[n].start=n;
30         v[n].end=n;
31         /**************处理得到每个元素的左右边界(一次遍历即可)***************/
32         stack<int> s;
33         int i=0;
34         while(i<(int)v.size()){
35             if(s.empty() || v[i].val > v[s.top()].val){
36                 //元素插入的时候可以得到其start
37                 v[i].start= s.empty() ? v[i].start : s.top()+1;
38                 s.push(i);
39                 ++i;
40             }
41             else{
42                 //元素弹出的时候可以知道其end,同时更新当前待入栈元素的start
43                 v[s.top()].end=i-1;
44                 v[i].start=v[s.top()].start;
45                 s.pop();
46             }
47         }
48 //        for(int i=0;i<n;++i){
49 //            cout<<"("<<v[i].val<<","<<v[i].start<<","<<v[i].end<<")"<<endl;
50 //        }
51 //        for(int i=0;i<n;++i){
52 //            cout<<inc[i]<<endl;
53 //        }
54         /******************得到每个元素的结果,返回最大值即可*****************/
55         long long result=0;
56         int index_start=0,index_end=0;//得到最大值的区间(这里是从0开始计数的)
57         for(int i=0;i<n;++i){
58             long long cur_result=v[i].val*(inc[v[i].end]-inc[v[i].start-1]);
59             if(cur_result>result){
60                 result=cur_result;
61                 index_start=v[i].start;
62                 index_end=v[i].end;
63             }
64         }
65         cout<<result<<"\n";
66         cout<<index_start+1<<" "<<index_end+1<<"\n";
67     }
68     return 0;
69 }

这段程序要注意几点:

  • 结果long long类型,因为int可能容纳不下;
  • inc数组要加个-1索引,为了计算第一个值对应的结果;
  • 正向遍历和反向遍历算出两个边界;如果只用一次也可以,但是时间复杂度就变成O(n^2)了(可以在push元素进栈的时候更新栈中的每个元素的end);
  • 代码输出了最大结果的区间标记,可以去掉;

总之,活学活用才是硬道理啊,一定要善于将知识转化为自己的本领。

另外,要读清楚题意,我做的时候直接把数组排了个序,以为可以乱序,结果直接从后向前遍历了,都是泪。。。

除此,这道题可以参见POJ2796,由于ACM系统没有针对STL的O2,我这段代码放进去是超时的,不想改了,想改的可以改成数组。

欢迎交流。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

查找排序数组的最小值(js)

在由小到大已排序的未知数组中,以某个元素为支点旋转(好比将序列沿着前后顺序围成环移动)得到了一个数组,请找出该数组的最小值。比如倘若原数组(对我们而言,并不知道...

19740
来自专栏JavaQ

HashMap在JDK1.8前后区别精简说

在JDK1.8以前版本中,HashMap的实现是数组+链表,它的缺点是即使哈希函数选择的再好,也很难达到元素百分百均匀分布,而且当HashMap中有大量元素都存...

36470
来自专栏小小挖掘机

Numpy基础知识点汇总

1、概述 Numpy是高性能科学计算和数据分析的基础包,它的部分功能如下: 1)ndarray,一个具有矢量算术运算和复杂广播能力的快速且节省空间的多维数组。 ...

32440
来自专栏计算机视觉与深度学习基础

Leetcode 31 Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically...

20950
来自专栏数据结构与算法

4939 欧拉函数

 时间限制: 1 s  空间限制: 1000 KB  题目等级 : 钻石 Diamond 题解 题目描述 Description 输入一个数n,输出小于n且与n...

33770
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

8620
来自专栏蜉蝣禅修之道

算法考试填数字问题

21020
来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

35340
来自专栏我的博客

C编程笔记

1.编译命令gcc test.c -o test 带上参数o就是指定编译文件名 2.printf(“%.2lf”,b) 其中前面2是小数点后位数,l是字母...

37250
来自专栏黑泽君的专栏

java基础学习_基础语法(下)02_day06总结

============================================================================= ==...

6210

扫码关注云+社区

领取腾讯云代金券