【单调栈】LeetCode:1944队列中可以看到的人数-阿里云开发者社区

【单调栈】LeetCode:1944队列中可以看到的人数

2024-01-22 21

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【单调栈】LeetCode:1944队列中可以看到的人数

题目

有 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 <= 10⁵

1 <= heights[i] <= 10⁵

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;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用C++ 实现。