住房和城乡规划建设局官方网站,html网页留言板代码,wordpress定制后台,网页版游戏平台【题目描述】 有 n 个人排成一个队列#xff0c;从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights #xff0c;每个整数 互不相同#xff0c;heights[i] 表示第 i 个人的高度。一个人能 看到 他右边另一个人的条件是这两人之间的所有人都比他们两人 矮 。更正式的从左到右 编号为 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 个人在他右侧队列中能 看到 的 人数 。 【题目链接】. - 力扣LeetCode
【解题代码】
package array;import common.Utils;import java.util.Arrays;
import java.util.Stack;public class CanSeePersonsCount {public static void main(String[] args) {//int heights[] {10, 6, 8, 5, 11, 9};//int heights[] {5, 1, 2, 3, 10};int[] heights Utils.readArrayFromFile(res\\1944\\40.txt);long start System.currentTimeMillis();System.out.println(开始计算。。。);int[] result canSeePersonsCount(heights);System.out.println(运行时长 (System.currentTimeMillis() - start) ms);System.out.println(计算结果: Arrays.toString(result));}public static int[] canSeePersonsCount(int[] heights) {int[] result new int[heights.length];StackInteger stack new Stack();stack.push(heights[heights.length - 1]);for (int i heights.length - 2; i 0; i--) {result[i] 1;while (heights[i] stack.peek()) {stack.pop();if (!stack.empty())result[i];else break;}stack.push(heights[i]);}return result;}}【解题思路】
拿到题目一开始想到的最简单思路就是位置i从0开始向后查找设置一个数值max记录当前最大身高目前位置的人是否能被看到取决于当前位置身高是否小于观测者并且大于max没被挡住,一直轮询直到数值大于当前值的位置或者最后一个人为止很快就完成代码编写
public int[] canSeePersonsCount1(int[] heights) {// 定义一个数组记录所有位置能看到的人数int[] result new int[heights.length];int max, j;for (int i 0; i heights.length - 1; i) {// 从当前位置右边第一个位置开始计算j i 1;// 定义当前位置右边遍历的最大身高max 0;// 向后依次轮询直到数值大于当前值的位置为止do {// 如果当前位置身高大于当前最大身高那么计数加1并更新当前最大身高if (heights[j] max) {result[i];max heights[j];}} while (heights[j] heights[i] j heights.length);}return result;
}
LeetCode试运行成果看来逻辑正确但这一道题毕竟是困难级别这种两种循环的简单低级算法代码提交肯定不能通过试了一下果不其然LeetCode系统报错超出时间限制 作为一个爱追根究底的程序员我把LeetCode系统报错的测试用例的数据拷贝到一个文件里然后本地加载运行看看到底需要运行多长时间相关加载数据代码
public static int[] readArrayFromFile(String fileName) {StringBuffer sb null;try {BufferedReader in new BufferedReader(new FileReader(fileName));while (in.ready()) {sb new StringBuffer(in.readLine());}} catch (Exception e) {return null;}String[] dataStrs sb.toString().split(,);return Arrays.stream(dataStrs).mapToInt(Integer::parseInt).toArray();
}
本地执行一下运行时长1656ms肯定不合格。这只是简单热个身接下来还是考虑专业的算法思路看到代码页面下面有5个英文提示翻译成中文如下
如何以二次复杂度解决这个问题-- 啥叫二次复杂度哥们要的是提示不是提问对于从索引 i 开始的每个子数组不断查找新的最大值直到找到大于 arr[i] 的值。--正确但无用的废话以哥们的智商这么简单的东西还要你来提示由于限制很高因此您需要线性解决方案。--又是正确但无用的废话当您从末尾到开头迭代数组时使用堆栈来保持数组值的排序。--哎堆栈这个提示有搞头继续看看下面怎么说。继续按排序顺序从堆栈中弹出元素直到找到大于 arr[i] 的值这些是我可以看到的值。--这句的意思好像是每次看到的人都是从堆栈依次弹出一直到大于当前位置身高值
根据后面两个稍微有用的提示反复思考终于有了眉目几点思路总结如下
最右一个人看到的人数是0因为右边没人了其它位置能看到的人数至少是1右边至少能看到1个人其它位置向右看到的身高肯定是一个比一个高因为小于当前位置身高的左边的人肯定看不到先将最右的人身高压栈从最右边第二个位置开始依次将栈中比当前身高矮的值出栈然后将当前位置压栈当前栈顶是右边第一个人身高后面肯定是一个比一个高
思路一打开解题就简单了且看下面解题步骤
【解题步骤】
定义一个数组记录所有位置能看到的人数 int[] result new int[heights.length]; 定义一个堆栈记录当前位置身高以及其右边“一个比一个高”的身高 StackInteger stack new Stack(); 将最右侧人身高压栈,最右侧的人看到的人数为0 stack.push(heights[heights.length - 1]); 从最右边第二个位置开始依次计算能看到的人数当前位置至少能看到右侧紧挨着的这个人 for (int i heights.length - 2; i 0; i--) {result[i] 1; 后从栈中弹出所有比当前位置身高矮的人这些都是当前位置能看到的人也都是左边位置都看不到的人 while (heights[i] stack.peek()) {stack.pop();if (stack.empty()) break;result[i];
} 再将当前位置身高压栈栈里此时状况是一山还比一山高 stack.push(heights[i]); 最后返回结果 return result;
【思考总结】
专业深入的思考之前可以简单的方式实现热热身LeetCode解题一个关键点就是需要掌握相关调试工具和技巧对于算法执行时间等性能指标要有清晰的数据这道题算法设计的关键点在于使用堆栈以及保存当前位置右侧所有的“一山还比一山高”的身高LeetCode解题之前可以看提示但一定不要看题解看了就“破功”了
