小Q在周末的时候和他的小伙伴来到大城市逛街,一条步行街上有很多高楼,共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋,小Q从来都没有见到这么多的楼,所以他想知道他在每栋楼的位置处能看到多少栋楼呢?(当前面的楼的高度大于等于后面的楼时,后面的楼将被挡住)
输入第一行将包含一个数字n,代表楼的栋数,接下来的一行将包含n个数字wi(1<=i<=n),代表每一栋楼的高度。1<=n<=100000;1<=wi<=100000;
输出一行,包含空格分割的n个数字vi,分别代表小Q在第i栋楼时能看到的楼的数量。
6 5 3 8 3 2 5
3 3 5 4 4 4
当小Q处于位置3时,他可以向前看到位置2,1处的楼,向后看到位置4,6处的楼,加上第3栋楼,共可看到5栋楼。当小Q处于位置4时,他可以向前看到位置3处的楼,向后看到位置5,6处的楼,加上第4栋楼,共可看到4栋楼。
import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int len = sc.nextInt(); int[] arr = new int[len]; for(int i = 0 ; i < len ; i++){ arr[i] = sc.nextInt(); } // stack中要保存的是 能看见的楼的 index int[] rightLook = new int[len]; Stack<Integer> stack = new Stack<>(); for(int i = len - 1 ; i >= 0 ; i--){ rightLook[i] = stack.size(); while((!stack.isEmpty()) && (arr[i] >= arr[stack.peek()])){ stack.pop(); } stack.push(i); } stack.clear(); for(int i = 0 ; i < len ; i++){ int total = rightLook[i] + 1 + stack.size(); while((!stack.isEmpty()) && (arr[i] >= arr[stack.peek()])){ stack.pop(); } System.out.print(total + " "); stack.push(i); } } }
if __name__=='__main__': n=int(input()) a = list(map(int, input().split())) #left right为栈 left=[] right=[] l_num=[] r_num=[] for i in range(len(a)):#向左看 l_num.append(len(left)) if(i==0):#第一个值特殊处理 left.append(a[i]) elif(a[i]<left[-1]):# 入栈操作 left.append(a[i]) else: while(len(left)!=0 and a[i]>=left[-1]): left.pop(-1) left.append(a[i]) a.reverse() for i in range(len(a)):#向右看 r_num.append(len(right)) if(i==0):#第一个值特殊处理 right.append(a[i]) elif(a[i]<right[-1]):# 入栈操作 right.append(a[i]) else: while(len(right)!=0 and a[i]>=right[-1]): right.pop(-1) right.append(a[i]) r_num.reverse() #print(l_num) #print(r_num) ans=[] for i in range(len(a)): ans.append(l_num[i]+r_num[i]+1) ansstr=' '.join([str(i) for i in ans]) print(ansstr)
// 递减栈 栈中元素数目即为能看到的楼数目 // 两个栈 一个表示向左能看到的数目 一个表示向右 注意所有栈都不考虑当前所在楼本身 因此最后结果要加1 // 以向右看为例 // 单调栈里维护了从最左边到该位置前递减序列 而到达当前位置的递减序列对于当前位置来 都是可见的 // 因此单调栈的大小保存了能看到楼的个数 import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Tencent2020backend2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] height = new int[n]; for(int i=0; i<n; i++) { height[i] = sc.nextInt(); } Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); ArrayList<Integer> count1 = new ArrayList<>(); ArrayList<Integer> count2 = new ArrayList<>(); for(int i = 0, j = height.length-1; i < height.length && j>=0; i++, j--) { count1.add(stack1.size()); count2.add(0, stack2.size()); while(!stack1.empty() && stack1.peek() <= height[i]) stack1.pop(); while(!stack2.empty() && stack2.peek() <= height[j]) stack2.pop(); stack1.push(height[i]); stack2.push(height[j]); } for(int i=0; i<n; i++) { System.out.print(count1.get(i) + count2.get(i) + 1 + " "); } } } // 递增栈 // for(int i=0; i<arr.size; i++) { // while(!stack.empty() && stack.peek() > arr[i]) stack.pop(); // } // 单增栈能以O(n)复杂度找到每一个元素的前下界 // 同理单减栈能以O(n)复杂度找到每一个元素的前上界 // 本题中到达前上界包含的位置数目即为能看到楼宇数 // 前上界之后的楼不可见
import java.util.Scanner; public class Tencent2 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int count = Integer.valueOf(scan.nextLine()); String s = scan.nextLine();//包含实际数组的字符串 outPut(s); } public static void outPut (String s){ String[] str = s.split(" "); int[] arr = new int[str.length]; //获取数组 for (int i = 0; i < str.length; i++) { arr[i] = Integer.valueOf(str[i]); } if (arr.length==1) { System.out.println("1");//排除长度为1的数组 }else if (arr.length==2) { System.out.println("2 2");//排除长度为2的数组 }else { for (int i = 0; i < arr.length; i++) {//剩余情况仅包含楼栋数>=3 if (i==0) { System.out.print(getCount(arr,i+1,true)+1+" ");//当处于第一栋楼的时候看到的数量 }else if ( i==arr.length-1) { System.out.print(getCount(arr,arr.length-i,false)+1);//当处于最后一栋楼看到的数量 }else { System.out.print(getCount(arr,i+1,true)+getCount(arr,arr.length-i,false)+1+" ");//当处于中间楼看到的数量 } } } } //获取倒序数组 public static int[] reverse(int[] a) { int[] b = new int[a.length]; for(int start=0,end=b.length-1;start<=end;start++,end--) { int temp=a[start]; b[start]=a[end]; b[end]=temp; } return b; } //获取当前朝向所看到的楼栋数(不包含本身所在楼) public static int getCount (int[] arrb,int j, boolean a) { int count = 1; if (!a) { arrb = reverse(arrb); } int max = arrb[j]; for (int i = j; i < arrb.length; i++) { if (arrb[i]>max) { max = arrb[i]; count++; } } return count; } }
let N = readline(); let Bu = readline(); let B = Bu.split(' ').map(Number); //B = B.map(Number); function buildingSaw(arrOri) { let len = arrOri.length; let arr = arrOri; let right= new Array(len); let stack = new Stack(); let resBuild = []; for (let i = len - 1; i >= 0; i--) { right[i] = stack.length(); while (stack.length() && arr[i] >= arr[stack.peek()]) { stack.pop(); } stack.push(i); } stack.clear(); for (let j = 0; j < len; j++) { let total = right[j] + 1 + stack.length(); while (stack.length() && arr[j] >= arr[stack.peek()]) { stack.pop(); } resBuild.push(total); stack.push(j); } return resBuild; } function Stack() { this.dataStore = []; //Init this.top = 0; //栈顶位置 this.pop = pop; //出栈 this.push = push; //入栈 this.peek = peek; //栈顶元素 this.length = length; //栈内元素总数 this.clear = clear; //清空栈 } function push(e) { this.dataStore[this.top++] = e; } function pop() { return this.dataStore[--this.top]; } function peek() { if (this.top > 0) return this.dataStore[this.top - 1]; else return 'Empty'; } function length() { return this.top; } function clear() { delete this.dataStore; this.dataStore = []; this.top = 0; } let result = buildingSaw(B).join(' '); console.log(result)
def buildings(n, nums): lstack, rstack = [nums[0]], [nums[n-1]] lrst, rrst =[1], [1] for i in range(1,n): lrst.append(len(lstack)+1) rrst.append(len(rstack)+1) while len(lstack)!=0 and nums[i]>=lstack[-1]:lstack.pop() while len(rstack)!=0 and nums[n-1-i]>=rstack[-1]:rstack.pop() lstack.append(nums[i]) rstack.append(nums[n-1-i]) rrst = [r for r in reversed(rrst)] res =[lrst[i] + rrst[i] -1 for i in range(n)] return res if __name__ == "__main__": n = int(input()) nums = list(map(int, input().split(' '))) res = buildings(n, nums) print(" ".join(list(map(str, res))))
import java.util.Scanner; import java.util.Stack; public class Main{ public static int[] MaxBuilding(int[] arr){ if(arr == null || arr.length < 0) return null; int[] res = new int[arr.length]; Stack<Integer> stack = new Stack<>(); // 从前向后遍历,维持一个递减栈 for(int i = 0;i < arr.length;i++){ res[i] = stack.size(); //前面能看到的数量 while(!stack.isEmpty() && arr[i] >= arr[stack.peek()]){ stack.pop(); } stack.push(i); } stack.clear(); // 从后向前遍历,同样维持递减栈 for(int i = arr.length - 1;i >=0;i--) { res[i] = res[i] + 1 + stack.size();;//后面能看到的数量 + 自己 while (!stack.isEmpty() && arr[i] >= arr[stack.peek()]) { stack.pop(); } stack.push(i); } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int len = sc.nextInt(); int[] arr = new int[len]; for(int i = 0 ; i < len ; i++){ arr[i] = sc.nextInt(); } int[] res = MaxBuilding(arr); for (int i = 0; i < res.length; i++) { System.out.print(res[i] + " "); } } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String[] strH = br.readLine().trim().split(" "); int[] h = new int[n]; for(int i = 0; i < n; i++) h[i] = Integer.parseInt(strH[i]); Stack<Integer> stack = new Stack<>(); // right[i]用来存储第i个位置向右看能看到的楼的数目 int[] right = new int[n]; for(int i = n - 1; i >= 0; i--){ right[i] = stack.size(); /* 保证栈是单调递增的,如果在向左遍历的过程中发现了比栈顶更高的楼i, 说明对于再往左一个位置的i-1而言,楼i后面更矮的楼是看不到的(高的能看到), 因此将比楼i高度小的楼全部弹出*/ while(!stack.isEmpty() && h[i] >= h[stack.peek()]) stack.pop(); // 比栈顶小,则往栈中添加 stack.push(i); } stack.clear(); // 往右看完了再往左看 for(int i = 0; i < n; i++){ // 右边+自己+左边 int totalI = right[i] + 1 + stack.size(); while(!stack.isEmpty() && h[i] >= h[stack.peek()]) stack.pop(); System.out.print(totalI + " "); stack.push(i); } } }
import java.util.*; public class Main { public static void main(String[] args) { // 获取输入 Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] heights = new int[n]; for (int i = 0; i < n; ++i) { heights[i] = scanner.nextInt(); } int[] result = new int[n]; // 从前向后遍历,维持一个递减栈 Stack<Integer> stack = new Stack<Integer>(); for (int i = 0; i < n; ++i) { result[i] += 1; // 自己所在位置 result[i] += stack.size(); // 前面能看到的楼数 // 维护栈 while (!stack.isEmpty() && stack.peek() <= heights[i]) { stack.pop(); } stack.push(heights[i]); } // 从后向前遍历,同样维持递减栈 stack.clear(); for (int i = n - 1; i >= 0; --i) { result[i] += stack.size(); // 后面能看到的楼数 // 维护栈 while (!stack.isEmpty() && stack.peek() <= heights[i]) { stack.pop(); } stack.push(heights[i]); } // 输出 for (int i = 0; i < n; ++i) { if (i != 0) { System.out.print(" " + result[i]); } else { System.out.print(result[i]); } } } }
const readline = require('readline') const rl = readline.createInterface({ input: process.stdin, ouput: process.stdout }) let inArr = [] rl.on('line',line=>{ if(!line) return inArr.push(line.trim()) if(inArr.length === 2){ let n = +inArr[0] let nArr = inArr[1].split(' ').map(e=>+e) let left = [], right = [], total = [] let stack =new Stack() for (let i = n-1; i>=0 ; i--) { right[i] = stack.length() while(right.length!=0 && nArr[i]>=nArr[stack.peek()]){ stack.pop() } stack.push(i) } stack.clear() for (let i = 0; i < n; i++) { total[i] = right[i] + stack.length()+1 left[i] = stack.length() while(left.length!=0 && nArr[i]>=nArr[stack.peek()]){ stack.pop() } stack.push(i) } // console.log(right) // console.log(left) console.log(total.join(' ')) } }) function Stack() { this.dataStore=[] this.top = 0 this.peek =peek this.pop =pop this.push =push this.length = length this.clear = clear } function push(e) { this.dataStore[this.top++] =e } function peek() { return this.dataStore[this.top-1] } function pop() { return this.dataStore[--this.top] } function clear() { this.top = 0 } function length() { return this.top }
#include<bits/stdc++.h> using namespace std; int vec[100005]; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> vec[i]; } vector<int> left(n); stack<int> sta; for (int i = 0; i < n; ++i) { left[i] = sta.size(); while (!sta.empty() && sta.top() <= vec[i]) { sta.pop(); } sta.push(vec[i]); } while (!sta.empty()) { sta.pop(); } vector<int> right(n); for (int i = n - 1; 0 <= i; --i) { right[i] = sta.size(); while (!sta.empty() && sta.top() <= vec[i]) { sta.pop(); } sta.push(vec[i]); } for (int i = 0; i < n; ++i) { cout << left[i] + 1 + right[i] << " "; } return 0; }
#include <iostream> #include <stack> #include <vector> using namespace std; // 6 // 5 3 8 3 2 5 int main() { int n = 0; while(cin >> n){ vector<int> hight(n); for(auto &i : hight) { cin >> i; } vector<int> ltor(n); vector<int> rtol(n); stack<int> s1; //从左往右记录遍历所有位置,ltor[i]是记录站在i栋楼处,能看到左边的多少栋楼 for (int i = 0; i < n; i++) { ltor[i] = s1.size(); //栈的size即为所能看到楼的数量 //如果栈不为空,且顶小于vi,则出栈, s1.top代表上一栋楼的高度, //如果当前楼高度高于上一栋楼,则表明当前位置(包括后面的楼)都看不到该楼,所以可以出栈, 且可以继续检查栈顶, //直到找到能符合条件的栈顶,此时size即为当前楼所能看到的左侧楼数量 while (!s1.empty() && s1.top() <= hight[i]) { s1.pop(); } // l0 = s1.size() = 0; // 将vi入栈, 第一次压入5, // i++, i = 1,l1 = 1, top = 5, 所以top>3, 不会弹出,压入v1 = 3, // i = 2, l2 = s1.size = 2, // ltor结果: 0 1 2 1 2 3 s1.push(hight[i]); } //测试 // for(auto i : ltor) // { // cout << i << " "; // } stack<int>s2; //从右往左遍历,记录当前位置能看到的右侧的楼的数量 for (int i = n - 1; i >= 0; i--) { rtol[i] = s2.size(); while (!s2.empty() && hight[i] >= s2.top()) { s2.pop(); } s2.push(hight[i]); } for (int i = 0; i < n; i++) { cout << ltor[i] + rtol[i] + 1 << " "; } cout << endl; } return 0; }
#include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; vector<int> a, b; stack<int> st1, st2; int main() { int n, x[100001]; cin >> n; int ans = 0; for (int i = 0; i < n; i++) cin >> x[i]; for (int i = 0, j = n - 1; i < n, j >= 0; i++, j--) { a.push_back(st1.size()); b.push_back(st2.size()); while (!st1.empty() && st1.top() <= x[i]) st1.pop(); while (!st2.empty() && st2.top() <= x[j]) st2.pop(); st1.push(x[i]); st2.push(x[j]); } reverse(b.begin(), b.end()); for (int i = 0; i < n; i++) cout << b[i] + a[i] + 1<< " "; return 0; }
#include <iostream> #include<vector> #include<deque> using namespace std; int returnMaxi(deque<int>&que,int &value){ int size = que.size(); for(int i=0;i<size;i++){ if(value>=que.back()){ que.pop_back(); }else break; } que.push_back(value); return size; } int main() { int n; cin>>n; vector<int> heights(n); vector<int> result(n,1); for(int i=0;i<n;i++){ int x; cin>>x; heights[i] = x; } deque<int> q1,q2; for(int i=n-1;i>=0;i--){ result[i] += returnMaxi(q1,heights[i]); result[n-1-i] += returnMaxi(q2,heights[n-1-i]); } for(int a:result){ cout<<a<<" "; } } // 64 位输出请用 printf("%lld")
let N = parseInt(readline()); let Bu = readline().split(' ').map(Number); const res = [] let stack = [] for(let i = 0; i < N; i ++){ res[i] = stack.length; while(stack[stack.length-1] <= Bu[i]) stack.pop(); stack.push(Bu[i]); } stack = [] for(let i = N-1; i >= 0; i --){ res[i] = res[i]+stack.length+1; while(stack[stack.length-1] <= Bu[i]) stack.pop(); stack.push(Bu[i]); } console.log(res.join(' '))
class Solution: def findBuilding(self, heights ): left=[] right=[] Lnum=[] Rnum=[] n = len(heights) - 1 for i in range(len(heights)): Lnum.append(len(left)) Rnum.append((len(right))) while len(left) != 0 and left[-1] <= heights[i]: left.pop() while len(right) != 0 and right[-1]<= heights[n]: right.pop() left.append(heights[i]) right.append(heights[n]) n = n-1 Rnum.reverse() #print(Lnum) #print(Rnum) b = [] for i in range(len(Lnum)): b.append(Lnum[i]+Rnum[i]+1) return b if __name__ == "__main__": heights = [5,3,8,3,2,5] s = Solution() b = s.findBuilding(heights) print(b)