首页 > 试题广场 > 逛街
[编程题]逛街
  • 热度指数:3894 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小Q在周末的时候和他的小伙伴来到大城市逛街,一条步行街上有很多高楼,共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋,小Q从来都没有见到这么多的楼,所以他想知道他在每栋楼的位置处能看到多少栋楼呢?(当前面的楼的高度大于等于后面的楼时,后面的楼将被挡住) 

输入描述:
输入第一行将包含一个数字n,代表楼的栋数,接下来的一行将包含n个数字wi(1<=i<=n),代表每一栋楼的高度。
1<=n<=100000;
1<=wi<=100000; 


输出描述:
输出一行,包含空格分割的n个数字vi,分别代表小Q在第i栋楼时能看到的楼的数量。
示例1

输入

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栋楼。
使用单调栈实现,开辟一个数组rightLook 保留往右看得到的数量,从右往左遍历,利用单调栈将看得到的数量保留在数组 rightLook 中 ,再从左往右遍历,获取往左看的计数。
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);
        }
     }
}


发表于 2020-02-12 22:07:34 回复(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;
}

发表于 2020-02-18 14:51:40 回复(5)
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;
}

}


编辑于 2020-03-15 07:32:11 回复(0)
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)


发表于 2020-01-12 16:34:10 回复(1)
/*    运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为50.00%    */
//有没有大佬讲解一下,多谢指正
#include<iostream>
using namespace std;

int main() {
    int w[100000],a[100000];
    int n;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    };

    for (int i = 0; i < n; i++) {
        int m = 0; //记录可见楼
        int temp1=0;    //记录可见楼的高度

        //前面可见楼
        for (int j =i; j +1< n; j++) {        
            if (w[j + 1] > temp1) {
                m++;
                temp1 = w[j + 1];
            };
        };

        int temp2 = 0;    //记录可见楼的高度
        //后面可见楼
        for (int j = i; j >0; j--) {
            if (w[j - 1] >temp2) {
                m++;
                temp2 = w[j - 1];
            };
        };
        a[i] = m + 1;  //前面和后面可见楼加上本身
    };

    for (int i = 0; i < n; i++) {
        cout << a[i] <<" ";
    };

    system("pause");
}
发表于 2020-05-13 10:26:03 回复(0)
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]);
            }
        }
    }
}
发表于 2020-03-19 21:11:31 回复(0)
JavScript 解法  发现还没人用js做出来😳 自己创建一个Stack 实例,问题迎刃而解😎
JS(Node)
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
}




发表于 2020-02-18 12:22:22 回复(0)
#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;
}

发表于 2020-01-13 16:56:57 回复(5)
def buildings(n, nums):
    lstack, rstack = [0], [0]
    op_nums = nums[::-1]
    left, right = [0, 1], [0, 1]
    for i in range(1, n - 1):
        if nums[i] < nums[i - 1]:
            lstack.append(i)
        else:
            while lstack and nums[i] > nums[lstack[-1]]:
                lstack.pop()
            lstack.append(i)
        if op_nums[i] < op_nums[i - 1]:
            rstack.append(i)
        else:
            while rstack and op_nums[i] > op_nums[rstack[-1]]:
                rstack.pop()
            rstack.append(i)
        left.append(len(lstack))
        right.append(len(rstack))
    res = []
    right = right[::-1]
    for i in range(n):
        res.append(left[i] + right[i] + 1)
    return res

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    res = buildings(n, nums)
    print(" ".join(list(map(str, res))))


第一时间用的暴力解法O(N^2)复杂度超时只能过40%
之后看了讨论大佬们用的单调栈的方法,写了一下python版本
发表于 2020-05-10 13:07:11 回复(0)
<?php
// 非要说我超时,我真没看出我哪里特别耗时,能通过40%
$num = fgets(STDIN);
$arr = explode(" ",trim(fgets(STDIN)));
$res = [];
foreach ($arr as $k => $v) {
    $n = 0;
    $max = 0;
    // 前面的
    for ($i = 1; $i <=$k;$i++) {
        if ($max < $arr[$k-$i]) {
            $n++;
            $max = $arr[$k-$i];
        } else {
            continue;
        }
    }
    // 后面的
    $max = 0;
    for ($i = $k+1; $i < $num;$i++) {
        if ($max < $arr[$i]) {
            $n++;
            $max = $arr[$i];
        } else {
            continue;
        }
    }
    $res[] = $n + 1;
}
echo implode(" ",$res);

发表于 2020-04-23 18:51:26 回复(0)
单调栈
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] + " ");
        }
    }

}

发表于 2020-04-12 00:23:15 回复(0)

感觉这个思路差不多,为什么只能80%。。

// 左右列表 空间换时间 80%
n = int(input())
w = list(map(int,input().split()))
right,left = n*[1],n*[1]
rlast,llast = 0,0
for i in range(n-1,-1,-1)://往右看能看到多少[含当前楼]
    if i == n-1:
        rlast = w[i]
        continue
    if w[i]<rlast:
        right[i] += right[i+1]
        rlast = w[i]
        continue
    for j in range(i+2,n):
        if w[j]>w[i]:
            right[i] += right[j]
            break
    rlast = w[i]
for i in range(n)://往左看能看到多少[含当前楼]
    if i == 0:
        llast = w[i]
        continue
    if w[i]<llast:
        left[i] += left[i-1]
        llast = w[i]
        continue
    for j in range(i-2,-1,-1):
        if w[j]>w[i]:
            left[i] += left[j]
            break
    llast = w[i]
//main
for i in range(n):
    cnt = 1
    if i>0:
        cnt+=left[i-1]
    if i+1<n:
        cnt+=right[i+1]
    print(cnt,end=' ')

//暴力 40%
'''
n = int(input())
w = list(map(int,input().split()))
for i in range(n):
    l,r = i-1,i+1
    cnt = 1
    lmax,rmax = 0,0
    while l>=0:
        if w[l]>lmax:
            cnt+=1
            lmax = w[l]
        l-=1
    while r<n:
        if w[r]>rmax:
            cnt+=1
            rmax = w[r]
        r+=1
    print(cnt,end=' ')
'''
发表于 2020-04-07 23:14:26 回复(0)
CPP来一个不一样的解法,不用单调栈,弹入弹出遍历需要时间,维护一个单调vector,直接用二分法查找并赋值,返回下标
int lhelper(vector<int>& res, int& right, int key) {
    int left = 0;
    int mid = 0;
    int tempr = right;
    while (left < tempr)
    {
        mid = (tempr + left) >> 1;
        if (res[mid] == key) {
            right = mid + 1;
            return mid;
        }
        else if (res[mid] > key)left = mid + 1;
        else tempr = mid;
    }
    if (tempr < 0)tempr = 0;
    res[tempr] = key;
    if (tempr == right)right++;
    else right = tempr + 1;
    return tempr;
}
int main() {
    int m;
    cin >> m;
    vector<int>resnow(m, 0);
    for (int i = 0; i < m; ++i) {
        cin >> resnow[i];
    }
    vector<int>lres(m, 0);
    int left = 0;
    vector<int>rres(m, 0);
    int right = 0;
    vector<int>res(m, 1);
    if (m == 1) {
        cout << resnow[0] << endl;
        return 0;
    }
    for (int i = 1; i < m; ++i) {
        res[i] += lhelper(lres, left, resnow[i - 1]) + 1;
    }
    for (int i = m - 2; i >= 0; --i) {
        res[i] += lhelper(rres, right, resnow[i + 1]) + 1;
    }
    for (auto i : res) {
        cout << i <<" ";
    }
    return 0;
 
}


发表于 2020-04-04 18:37:14 回复(0)
package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

func string2int(list []string) []int {
    r := []int{}
    for _, v := range list {
        i, _ := strconv.ParseInt(v, 10, 0)
        r = append(r, int(i))
    }
    return r
}

func int2string(list []int) []string {
    r := []string{}
    for _, v := range list {
        s := strconv.FormatInt(int64(v), 10)
        r = append(r, s)
    }
    return r
}

func findLeft(i, n int, w []int) int {
    left := 0
    leftMax := 0
    for j := i - 1; j >= 0; j-- {
        if w[j] > leftMax {
            left++
            leftMax = w[j]
        }
    }
    return left
}

func findRight(i, n int, w []int) int {
    right := 0
    rightMax := 0
    for j := i + 1; j < n; j++ {
        if w[j] > rightMax {
            right++
            rightMax = w[j]
        }
    }
    return right
}

func readLine() string {
    s := bufio.NewScanner(os.Stdin)
    s.Scan()
    return s.Text()
}

func main() {
    //nTemp := "6"
    //wTemp := "5 3 8 3 2 5"
    nTemp := readLine()
    wTemp := readLine()
    r := []int{}
    nInt64, _ := strconv.ParseInt(nTemp, 10, 32) /*int64*/
    n := int(nInt64)                             /*int*/
    wString := strings.Split(wTemp, " ")         /*[]string*/
    w := string2int(wString)                     /*[]int*/
    for i, _ := range w {
        r = append(r, findLeft(i, n, w)+findRight(i, n, w)+1)
    }
    rString := int2string(r)
    fmt.Println(strings.Join(rString, " "))
}
我的go代码本地测试通过的,不晓得怎么回事?
发表于 2020-04-03 12:45:35 回复(0)
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        //dp[index][0]: 表示在index+1栋楼处可以看到左边多少栋楼
        //dp[index][1]: 表示在index+1栋楼处可以看到右边多少栋楼
        //dp[index][2]: 表示在index+1栋楼左边或者右边第一栋大于当前楼的楼的位置
        int[][] dp = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
            if (i > 1 && arr[i - 1] > arr[i - 2]) {
                //当前楼的左边第一栋楼大于第二栋楼高度
                int index = dp[i - 1][2];
                if (index == -1)
                    //等于-1表明当前楼左边第一栋楼将左边的所有楼挡住了
                    dp[i][0] = 1;
                else
                    dp[i][0] = dp[index + 1][0] + 1;
            } else if (i > 1 && arr[i - 1] < arr[i - 2]) {
                //当前楼左边第一栋楼小于第二栋楼高度
                dp[i][0] = dp[i - 1][0] + 1;
                dp[i][2] = i - 1;
            } else if (i > 1 && arr[i - 1] == arr[i - 2]) {
                dp[i][0] = dp[i - 1][0];
            } else if (i == 1) {
                dp[1][0] = 1;
                if (arr[1] >= arr[0])
                    dp[1][2] = -1;
            } else
                dp[i][2] = -1;
            if (i > 1 && i < n - 1) {
                //更新左边比当前楼高的楼的位置
                if (arr[i] < arr[i - 1])
                    dp[i][2] = i - 1;
                else if (arr[i] == arr[i - 1])
                    dp[i][2] = dp[i - 1][2];
                else {
                    int index = dp[i - 1][2];
                    while (index > -1 && arr[i] >= arr[index]) {
                        index = dp[index][2];
                    }
                    dp[i][2] = index;
                }
            }
        }
        scanner.close();
        dp[n - 1][2] = n;
        for (int i = n - 2; i >= 0; i--) {
            if (i < n - 2 && arr[i + 1] > arr[i + 2]) {
                int index = dp[i + 1][2];
                if (index == n)
                    dp[i][1] = 1;
                else
                    dp[i][1] = dp[index - 1][1] + 1;
            } else if (i < n - 2 && arr[i + 1] < arr[i + 2]) {
                dp[i][1] = dp[i + 1][1] + 1;
            } else if (i < n - 2 && arr[i + 1] == arr[i + 2]) {
                dp[i][1] = dp[i + 1][1];
            } else if (i == n - 2) {
                dp[i][1] = 1;
                if (arr[i] >= arr[i + 1])
                    dp[i][2] = n;
                else
                    dp[i][2] = n - 1;
            }
            if (i < n - 1 && i > 0) {
                if (arr[i] < arr[i + 1])
                    dp[i][2] = i + 1;
                else if (arr[i] == arr[i + 1])
                    dp[i][2] = dp[i + 1][2];
                else {
                    int index = dp[i + 1][2];
                    while (index < n && arr[i] >= arr[index]) {
                        index = dp[index][2];
                    }
                    dp[i][2] = index;
                }
            }
        }
        //经测试,输出较多用StringBuilder存好,一次输出可以减少时间,输出是线程安全的,比较耗费时间
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            builder.append(dp[i][0] + dp[i][1] + 1 + " ");
        }
        System.out.print(builder);
    }
}

发表于 2020-04-02 21:47:35 回复(0)
#include <iostream>
using namespace std;
int *h, *dp, *dp1, n;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    h = new int[n];
    dp = new int[n];
    dp1 = new int[n];
    for (int i = 0; i < n; i++)
        cin >> h[i];
    dp1[n - 1] = dp[0] = 0, dp1[n - 2] = dp[1] = 1;
    for (int i = n - 3; i >= 0; i--){
        int j = i + 1;
        while (h[j + 1] <= h[i + 1] && j + 1 < n)j++;
        dp1[i] = dp1[j] + 1;
    }
    cout<<dp1[0]+1<<" "<<dp1[1]+2<<" ";
    for (int i = 2; i < n; i++){
        int j = i - 1;
        while (h[j - 1] <= h[i - 1] && j - 1 >= 0)j--;
        dp[i] = dp[j] + 1;
        cout << dp[i] + dp1[i]+1<<" ";
    }
}
上面这个代码超时了
修改为单调栈就过了
#include <iostream>
#include<stack>
using namespace std;
int h[100001], dp[100001], n;
int main(){
    cin >> n;
    for (int i = 0; i < n; i++)cin >> h[i];
    stack<int> l,r;
    for(int i=n-1;i>0;i--){
        while (!r.empty()&&h[i]>=r.top())r.pop();
        r.push(h[i]);
        dp[i-1]=r.size();
    }
    cout<<dp[0]+1<<" ";
    for(int i=0;i<n-1;i++){
        while (!l.empty()&&h[i]>=l.top())l.pop();
        l.push(h[i]);
        dp[i+1]+=l.size()+1;
        cout<<dp[i+1]<<" ";
    }
}


编辑于 2020-03-13 15:58:40 回复(0)
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
public class Main{
public static void main(String[] args){
List<Integer> ls = new ArrayList<>();//记录输入
Scanner in = new Scanner(System.in);
while(in.hasNextInt()) {
ls.add(in.nextInt());
}
int inputNum=ls.get(0);
int[] inputArr = new int[inputNum];
for(int i=1;i<inputNum+1;i++){
inputArr[i-1]=ls.get(i);
}
int[] outs = new int[inputNum];
Stack<Integer> stack1 = newStack<>();
int deep=0;//记录栈的深度
//向左看
for(int i=0;i<inputNum;i++){
if(stack1.empty()||stack1.peek()>inputArr[i]){
if(!stack1.empty()&&stack1.peek()>inputArr[i]){
outs[i]+=deep;
}
stack1.push(inputArr[i]);
deep++;
}else{
while(!stack1.empty()&&inputArr[i]>=stack1.peek()){
outs[i]+=1;
stack1.pop();
deep--;
}
outs[i]+=deep++;
stack1.push(inputArr[i]);
}
}
//向右看
stack1.clear();
deep=0;
int[] outs2=newint[inputNum];
for(int i=inputNum-1;i>=0;i--){
if(stack1.empty()||stack1.peek()>inputArr[i]){
if(!stack1.empty()&&stack1.peek()>inputArr[i]){
outs2[i]+=deep;
}
stack1.push(inputArr[i]);
deep++;
}else{
while(!stack1.empty()&&inputArr[i]>=stack1.peek()){
outs2[i]+=1;
stack1.pop();
deep--;
}
outs2[i]+=deep++;
stack1.push(inputArr[i]);
}
}
//整理输出
for(int i=0;i<inputNum;i++){
if(i==(inputNum-1)){
System.out.print((outs[i]+outs2[i]+1));
}else{
System.out.print((outs[i]+outs2[i]+1)+" ");
}
}
}
}
编辑于 2020-02-23 22:18:58 回复(0)
%
发表于 2020-02-15 16:21:00 回复(0)
单调栈,双向的
n = int(input().strip())
l = list(map(int, input().strip().split()))

def handle(heights: list):
    stack = []
    res = [0] * n
    for i in range(n):
        res[i] = len(stack)
        if i == 0:
            stack.append(heights[0])
        elif stack[-1] > heights[i]:
            stack.append(heights[i])
        else:
            while stack and stack[-1] <= heights[i]:
                stack.pop()
            stack.append(heights[i])
    return res

resA = handle(l)
resB = handle(l[::-1])[::-1]
res = [resA[i] + resB[i] + 1 for i in range(n)]

print(" ".join(list(map(str, res))))


发表于 2020-02-04 12:19:23 回复(2)
#include<bits/stdc++.h>
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
 
const int maxn = 100005;
 
int n;
int h[ maxn ];
int r[ maxn ], l[ maxn ];
 
stack< int > s;
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    s.push( h[ n ] );
    r[ n ] = 0;
    for (int i = n - 1; i >= 1; i--)
    {
        r[ i ] = s.size();
        while( ( !s.empty() ) && s.top() <= h[ i ] ) s.pop();
        s.push( h[ i ] );
    }
    while( !s.empty() ) s.pop();
    s.push( h[ 1 ] );
    l[ 1 ] = 0;
    for (int i = 2; i <= n; i ++ )
    {
        l[ i ] = s.size();
        while( ( !s.empty() ) && s.top() <= h[ i ] ) s.pop();
        s.push( h[ i ] );
    }
    for( int i = 1; i <= n - 1; i ++ ) cout << l[ i ] + r[ i ] + 1 << " ";
    cout << l[ n ] + r[ n ] + 1 << endl;
    return 0;
}

发表于 2020-02-02 01:15:06 回复(0)