一.
P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）
如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。
思路：容易看出，当一个点满足x轴或y轴任意一个坐标比以存在的点的x轴或y轴的坐标大，即为以存在的点的“最大”。因此可以考虑先将点按x轴做坐标排序，然后对y轴维护一个单调非增的栈 。栈中的点即为”最大的”。
因其内存限制，下面代码ac 80%：
n=int(raw_input()) ps=[] for _ in range(n): x,y=raw_input().split(' ') ps.append((int(x),int(y))) ps.sort() stack_ele_num=1 i=1 while i<n: cur_p=ps[stack_ele_num] while stack_ele_num and cur_p[1]>ps[stack_ele_num-1][1]: ps.pop(stack_ele_num-1) stack_ele_num-=1 stack_ele_num+=1 i+=1 for p in ps: print '%s %s'%(p[0],p[1])二. 给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：
区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列 [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:
[6] = 6 * 6 = 36;
[2] = 2 * 2 = 4;
[1] = 1 * 1 = 1;
[6,2] = 2 * 8 = 16;
[2,1] = 1 * 3 = 3;
[6, 2, 1] = 1 * 9 = 9;
从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。
区间内的所有数字都在[0, 100]的范围内;
输入描述: 第一行输入数组序列长度n，第二行输入数组序列。 对于 50%的数据, 1 <= n <= 10000; 对于 100%的数据, 1 <= n <= 500000;
输出描述: 输出数组经过计算后的最大值。 示例1 输入 3 6 2 1 输出 36
思路：对于数组中的每一数字，我们需要找到以该个数字 为最小值但和最大的区间。以[2,6,5,4,1]为例： 那么我们首先想到的是暴力方法：对应每一个数字，向两边扩展，直到有一个值小于之或到达尽头停止，统计扩展经过的数字之和。但时间复杂度为O(n^2)。
既然需要找到两边较小的值，那么我们定义一个单调非减的栈，当栈顶为空或栈顶小于等于当前数值时，当前数值入栈。若栈顶大于当前数值，栈顶出栈，累计当前栈的出栈总和，再加上之前出栈的值之和，计算取最值即可。由于要统计当前数值出栈之和以方便计算之前出栈值，需要添加一个辅助栈，记录单调非减栈出栈之和，下面是该算法过程：
下面为代码：
n=int(raw_input()) arr=[int(x) for x in raw_input()[:-1].split(' ')] arr.append(-1) i=0 stack_pop_before=[] stack=[] ans=0 while i<=n: num=arr[i] pop_sum=0 pop_before=0 while stack and num<stack[-1]: pop_num=stack.pop() pop_sum+=pop_num pop_before+=stack_pop_before.pop() ans=max(ans,(pop_before+pop_sum)*pop_num) stack_pop_before.append(pop_before+pop_sum) stack.append(num) i+=1 print ans