题目链接
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
string s;
void get_ans(vector<int>& nums) {
stack<int> st1;
stack<int> st2;
// 先初始化答案为1,因为至少包括自己这栋楼
vector<int> visible(nums.size(), 1);
// 从左向右遍历数组
for(int i = 0; i < nums.size(); ++i) {
// 此时栈中的元素大小就是往左边看能看到的大楼数量
visible[i] += st1.size();
// 保证栈顶元素比nums[i]要大,把在栈顶但比nums[i]小的全部弹出
// 因为高度比nums[i]低且在它左边的楼都将被遮住
while(!st1.empty() && nums[i] >= st1.top()) {
st1.pop();
}
// 此时比nums[i]小的都已经被弹出
// 将nums[i]加入栈顶
st1.push(nums[i]);
}
// 从右向左遍历数组,与上方同理
for(int i = nums.size() - 1; i >= 0; --i) {
visible[i] += st2.size();
while(!st2.empty() && nums[i] >= st2.top()) {
st2.pop();
}
st2.push(nums[i]);
}
//输出答案
cout << "[";
for(int i = 0; i < visible.size(); ++i) {
if(i == visible.size() - 1) {
cout << visible[i];
}
else {
cout << visible[i] << ",";
}
}
cout << "]" << endl;
}
int main() {
while(cin >> s) {
// 处理数据并存入nums数组
vector<int> nums;
int tmp = 0;
for(int i = 1; i < s.size(); ++i) {
if(s[i] == ']' || s[i] == ',') {
nums.push_back(tmp);
tmp = 0;
}
else {
tmp = tmp * 10;
tmp += (int)(s[i] - 48);
}
}
get_ans(nums);
}
return 0;
}import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
/*
题意为计算在每栋楼的位置处可以看到多少栋楼，考虑了从左向右和从右向左两个方向的可见性。可以使用单调栈的特性进行解决。
这里是代码的主要思路：
首先将 visibleCounts 每个位置上的值加 1（因为包括自己本身的楼）。
从左向右遍历楼的高度数组 heights，使用栈 stack1 来保存之前遇到的楼的高度，保证栈顶元素总是比后面的元素要高。在遍历过程中，对于每一栋楼，将栈的大小（即之前楼的数量）存储在 visibleCounts 数组中的对应位置，表示往左看能看到的楼的数量。如果当前楼高度大于等于栈顶元素，则不断将栈顶元素弹出，直到满足条件。
从右向左遍历楼的高度数组 heights，使用栈 stack2 来保存之前遇到的楼的高度，保证栈顶元素总是比后面的元素要高。在遍历过程中，对于每一栋楼，将栈的大小（即之前楼的数量）加到 visibleCounts 数组中的对应位置，表示往右看能看到的楼的数量。如果当前楼高度大于等于栈顶元素，则不断将栈顶元素弹出，直到满足条件。
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String buildings = scanner.nextLine();
int[] heights = parseIntArray(buildings);
int n = heights.length;
int[] visibleCounts = new int[n];
Arrays.fill(visibleCounts, 1);
calculateVisibleCounts(heights, visibleCounts);
System.out.println(Arrays.toString(visibleCounts).replaceAll(" ", ""));
}
public static void calculateVisibleCounts(int[] heights, int[] visibleCounts) {
int n = heights.length;
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
for (int i = 0; i < n; i++) {
visibleCounts[i] += stack1.size();
while (!stack1.empty() && stack1.peek() <= heights[i]) {
stack1.pop();
}
stack1.push(heights[i]);
}
for (int i = n - 1; i >= 0; i--) {
visibleCounts[i] += stack2.size();
while (!stack2.empty() && stack2.peek() <= heights[i]) {
stack2.pop();
}
stack2.push(heights[i]);
}
}
public static int[] parseIntArray(String input) {
String[] elements = input.substring(1, input.length() - 1).split(",");
int[] parsedArray = new int[elements.length];
for (int i = 0; i < elements.length; i++) {
parsedArray[i] = Integer.parseInt(elements[i].trim());
}
return parsedArray;
}
}###################
# 第33题
###################
#
# #小明在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有 n 座高楼排成一行。
# 小明从第一栋一直走到了最后一栋，小明从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）
#
# 思路：利用单调栈，先从头到尾进行遍历得到向正方向看能看得到的楼数目，再reverse数组，计算得到反方向看楼的数目，最终将两个数组相加
def get_Num(nums):
res = [0 for _ in nums]
stack = [0]
# 从头遍历，站在每个位置上向前看能看到的楼的数量，不管怎样在1号楼都能看见0号楼，同时，保证单调栈内单调递减
for i in range(1, len(nums)):
res[i] = len(stack)
while len(stack) != 0 and nums[stack[-1]]<=nums[i]:
stack.pop()
stack.append(i)
return res
s = input()
try:
nums = eval(s)
except:
print("error for input")
frot = get_Num(nums=nums)
nums.reverse()
back = get_Num(nums=nums)
for i in range(len(frot)):
frot[i] += back[len(frot)-1-i] + 1
print("[" + ",".join(map(str, frot)) + "]")