平台网站建设有哪些,智慧软文发布系统,企业培训课程有哪些,做电力招聘的有哪些网站大家好#xff0c;我是星恒 今天是一道困难题#xff0c;他的题解比较好理解#xff0c;但是不好想出来#xff0c;接下来就让我带大家来捋一捋这道题的思路#xff0c;以及他有什么特征 题目#xff1a;leetcode 1944有 n 个人排成一个队列#xff0c;从左到右 编号为 … 大家好我是星恒 今天是一道困难题他的题解比较好理解但是不好想出来接下来就让我带大家来捋一捋这道题的思路以及他有什么特征 题目leetcode 1944有 n 个人排成一个队列从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights 每个整数 互不相同heights[i] 表示第 i 个人的高度。一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的第 i 个人能看到第 j 个人的条件是 i j 且 min(heights[i], heights[j]) max(heights[i1], heights[i2], …, 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.length1 n 1051 heights[i] 105heights 中所有数 互不相同 。
分析看到这道题大家第一想到的一定是枚举每一种情况然后依次与每一个值比较记录比当前值大的值当然他的时间复杂度是O(n2)他的作用只能是为我们提供一些信息最大都是O(n2)说明优化大概率是O(n) 或者 O(nlogn)我们可以想到的方法二分利用一些特殊的数据结构动归等等。很明显这道题不能使用二分因为没有折半的判断条件呀所以我们可以拓展其他思维
从题目中的例子可以看出对于某个人他可以看到 比它小的人并且这些人的规律是 单调递增ok看到单调性我们肯定能想到这个数据结构单调栈没错这道题的思路就是单调栈但难点就在如何使用单调栈
由于前面的看到的是一个单调递增的序列并且我们需要从后向前来维护所以我们维护一个从栈底到栈顶递减的一个栈。同样由于前面的人看不到被后面的人挡住的比其后面的这个人小的人即使这个人比它小所以我们可以直接把他抛弃掉这样前面的人只要将栈里面比它小的人统计就可以知道它可以看多少人了当然统计后出栈即可因为它挡住了前面的视线看比它小的人的视线
题解
class Solution {public int[] canSeePersonsCount(int[] heights) {int n heights.length;DequeInteger stack new ArrayDequeInteger();int[] res new int[n];for (int i n - 1; i 0; i--) {int h heights[i];while (!stack.isEmpty() stack.peek() h) {stack.pop();res[i];}if (!stack.isEmpty()) {res[i];}stack.push(h);}return res;}
}如果大家有什么思考和问题可以在评论区讨论也可以私信我很乐意为大家效劳。好啦今天的每日一题到这里就结束了如果大家觉得有用可以可以给我一个小小的赞呢我们下期再见 这里和大家说声不好意思这周从元旦开始都没有发帖子尤其每日一题对不起 原因是这今天都计划上午写贴子晚上发贴子但是由于这几天回了家里稍微有点忙并且和在学校相比有些许不适应所以一直没有顾上发但其实我每天都在坚持写今天我们把我这周攒下的每日一题都发出来了大家感兴趣的可以去看看让我们一起进步 ~~~
