作者推荐
题目
有 n 个人排成一个队列，从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights ，每个整数 互不相同，heights[i] 表示第 i 个人的高度。
一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的，第 i 个人能看到第 j 个人的条件是 i < j 且 min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], …, heights[j-1]) 。
请你返回一个长度为 n 的数组 answer ，其中 answer[i] 是第 i 个人在他右侧队列中能 看到 的 人数 。
示例 1：
输入：heights = [10,6,8,5,11,9]
输出：[3,1,2,1,1,0]
解释：
第 0 个人能看到编号为 1 ，2 和 4 的人。
第 1 个人能看到编号为 2 的人。
第 2 个人能看到编号为 3 和 4 的人。
第 3 个人能看到编号为 4 的人。
第 4 个人能看到编号为 5 的人。
第 5 个人谁也看不到因为他右边没人。
示例 2：
输入：heights = [5,1,2,3,10]
输出：[4,1,1,1,0]
提示：
n == heights.length
1 <= n <= 105
1 <= heights[i] <= 105
heights 中所有数 互不相同 。
分析
从右向左遍历所有人(i从大到小）,sta记录所有右边的人。如果i1 < i2，且heights[i1] > hights[i2]，则前面的任何人到看不到i2，被i1所挡。淘汰i2后，sta从栈底到栈顶降序。
如果当前元素高于栈顶元素，则当前元素看得到栈顶。两者之间没有人高于等于栈顶之人，否则栈顶之人早出栈了。
注意：栈顶第一个高于等于当前人也可以看到，只是看不到后面的人。
时间复杂度: o(n)，每个人顶多出栈入栈一次。
代码
核心代码
class Solution { public: vector<int> canSeePersonsCount(vector<int>& heights) { m_c = heights.size(); vector<int> vRet(m_c); stack<int> sta; for (int i = m_c - 1; i >= 0; i--) { while (sta.size() && (sta.top() < heights[i])) { vRet[i]++; sta.pop(); } vRet[i] += !sta.empty(); while (sta.size() && (sta.top()== heights[i])) { sta.pop(); } sta.emplace(heights[i]); } return vRet; } int m_c; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> heights; { Solution slu; heights = { 10,6,8,5,11,9 }; auto res = slu.canSeePersonsCount(heights); Assert({ 3,1,2,1,1,0 }, res); } { Solution slu; heights = { 5,1,2,3,10 }; auto res = slu.canSeePersonsCount(heights); Assert({ 4,1,1,1,0 }, res); } //CConsole::Out(res); }
2023年3月版：二分查找
class Solution { public: vector canSeePersonsCount(vector& heights) { m_c = heights.size(); vector vRet(m_c); vector vDescHeight; for (int i = m_c - 1; i >= 0; i–) { auto iNum = std::upper_bound(vDescHeight.begin(), vDescHeight.end(), heights[i],std::greater()) - vDescHeight.begin(); if (iNum > 0) { vRet[i] = vDescHeight.size() - (iNum - 1); } else { vRet[i] = vDescHeight.size(); } while (vDescHeight.size() && (vDescHeight.back() <= heights[i])) { vDescHeight.pop_back(); } vDescHeight.push_back(heights[i]); } return vRet; } int m_c; };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。
