Nothing up here. The good stuff is below.
Powered by Randall
定义数组或者栈;
for (遍历原始数据数组){
if (栈空 栈顶元素大于等于当前比较元素){
入栈;
}
else{
while (栈不为空 && 栈顶元素小于当前元素){
栈顶元素出栈;
更新结果;
}
当前数据入栈;
}
}
- 小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）
- 当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。
函数代码（利用动态数组ArrayList模拟栈）#
public static int[] findBuilding(int[] heights) {
int[] number = new int[heights.length];
ArrayList < Integer > LTR = new ArrayList < Integer > (); // 从大到小（从左往右从大到小）
ArrayList < Integer > RTL = new ArrayList < Integer > (); // 从小到大（从右往左从大到小）
for (int i
public static int[] findBuilding(int[] heights) {
int[] number = new int[heights.length];
Stack < Integer > LTR = new Stack < > (); // 从大到小（从左往右从大到小）
Stack < Integer > RTL = new Stack < > (); // 从小到大（从右往左从大到小）
for (int i = 0, j =
#include <stdio.h>
int main() {
int i,n,j, x[100001],LtoR[100001],RtoL[100001],sum[100001];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf(
=
0
, j
=
number.length
-
1
; i
<
number.length; i
++
, j
--
) {
// 每次i，j游标指向的是小Q所在的房子的左边的房子或者右边的房子在内的单调栈
// 因为第一次循环的时候是最左边的房子和最右边的房子入栈，所以要先记录左右两边单调栈里的数
// 且最后一次循环不出现问题，LYT单调栈到最右边的时候即不出现最右边的房子为某个房子左边的房子，RTL同理
number[i] += LTR.size();
number[j] += RTL.size();
while (LTR.size() > 0 && heights[i] > (int) LTR.get(LTR.size() - 1)) {
LTR.remove(LTR.size() - 1); // LTR出栈
}
while (RTL.size() > 0 && heights[j] > (int) RTL.get(RTL.size() - 1)) {
RTL.remove(RTL.size() - 1); // RT出栈
}
LTR.add(heights[i]); // LTR入栈
RTL.add(heights[j]); // RTL入栈
}
for (int i = 0; i < number.length; i++) {
number[i] ++;
}
return number;
}
number.length
-
1
; i
<
number.length; i
++
, j
--
) {
// 每次i，j游标指向的是小Q所在的房子的左边的房子或者右边的房子在内的单调栈
// 因为第一次循环的时候是最左边的房子和最右边的房子入栈，所以要先记录左右两边单调栈里的数
// 且最后一次循环不出现问题，LYT单调栈到最右边的时候即不出现最右边的房子为某个房子左边的房子，RTL同理
number[i] += LTR.size();
number[j] += RTL.size();
while (!LTR.isEmpty() && heights[i] > LTR.peek()) {
LTR.pop(); // LTR出栈
}
while (!RTL.isEmpty() && heights[j] > RTL.peek()) {
RTL.pop(); // RT出栈
}
LTR.push(heights[i]); // LTR入栈
RTL.push(heights[j]); // RTL入栈
}
for (int i = 0; i < number.length; i++) {
number[i] ++;
}
return number;
}
"
%d
"
,
&
x
[i]);
int indl=0,indr=0;
for(i=0,j=n-1;i<n,j>=0;i++,j--){
sum[i]+=indl;
sum[n-i-1]+=indr;
//从左往右遍历（从右往左看）
while(LtoR[indl-1]<=x[i]&&indl>0){
indl --;//出栈操作
}
//从右往左遍历（从左往右看）
while(RtoL[indr-1]<=x[j]&&indr>0){
indr --;//出栈操作
}
LtoR[indl]=x[i];//入栈
indl ++;
RtoL[indr]=x[j];//入栈
indr ++;
}
//注意加一
for(i=0;i<n-1;i++){
printf("%d ",sum[i]+1);
}
printf("%d\n",sum[n-1]+1);
return 0;
}