騰訊2020校園招聘----逛街

文章目錄

• • 騰訊2020校園招聘----逛街
  • 一、問題描述
  • 二、問題分析

一、問題描述

小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

輸出例子1:

3 3 5 4 4 4

例子說明1:

當小Q處于位置3時，他可以向前看到位置2,1處的樓，向后看到位置4,6處的樓，加上第3 棟樓，共可看到5棟樓。當小Q處于位置4時，他可以向前看到位置3處的樓，向后看到位置 5,6處的樓，加上第4棟樓，共可看到4棟樓。

二、問題分析

這題比較簡單，屬于單調棧類問題；
單調棧

直接看代碼：

方法一：暴力解法（超時）

#include <iostream> #include <vector> #include <stack> using namespace std;int main() {int n;while(cin>>n){vector<int> arr(n);for(int i = 0;i < n;i++){cin>>arr[i];}for(int i = 0;i < n;i++){stack<int> s1;stack<int> s2;for(int j = i - 1;j >= 0;j--){if(s1.empty() || s1.top() < arr[j])s1.push(arr[j]);}for(int j = i + 1;j < n;j++){if(s2.empty() || s2.top() < arr[j])s2.push(arr[j]);}cout<<s1.size() + s2.size() + 1<<" ";}}return 0; }

暴力的方法是遍歷數組中的每個元素，對每個元素的左邊和右邊分別根據單調棧的性質把元素放進兩個棧中，最后返回兩個棧中的元素個數之和+1；

這就相當于對每個元素都有n的復雜度，整個就接近$log(n2)$,復雜度太高

方法二、優化

• 既然復雜度太高，我們就一趟從前往后遍歷找到所有位置滿足情況的元素的個數
• 再一趟從后往前遍歷找到所有位置滿足情況的元素的個數
• 最后把二者相加就是結果

#include <iostream> #include <stack> #include <vector> using namespace std;int main() {int n;cin >> n;vector<int> arr(n);vector<int> dp(n);//保存從前往后和從后往前遍歷的結果for (int i = 0; i < n; i++)cin >> arr[i];stack<int> l,r;//單調棧//從后往前遍歷，找到每個位置后面能看到的房子個數for(int i = n-1;i > 0;i--){//如果棧頂元素比當前元素小，說明我這個高個子擋住后面矮個子的房子了//那么從當前位置往后面看，肯定就看不到矮個子的房子，只看到高個子的房子//所以可以直接pop掉矮個子的房子while (!r.empty() && arr[i] >= r.top())r.pop();r.push(arr[i]);dp[i - 1] = r.size();}//注意邊界問題：從后往前沒有計算到0，在1的時候就把0計算了cout<<dp[0] + 1<<" ";//從后往前遍歷，找到每個位置前面能看到的房子個數for(int i = 0;i < n-1;i++){//同理while (!l.empty() && arr[i] >= l.top())l.pop();l.push(arr[i]);dp[i + 1] += l.size() + 1;cout<<dp[i + 1]<<" ";} }

總結

以上是生活随笔為你收集整理的腾讯2020校园招聘----逛街的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。