2022-02-05 18:47:57
1. 问题
如果有若干个数字，输入其中所有最小的数字。
例如，输入1 2 3 1 2 1 4 5，则输出1 1 1
2. 思路
2.1 思路1
最简单的思路是排序，按从小到大排序后，第一个就是最小的数字，然后从第一个往后遍历，等于最小数字的输出即可。但是这种方案需要两层循环，时间复杂度是O(n^2)，应该寻求更快的方案。
2.2 思路2
想一下人如果去干这件事怎么实现，首先是找到最小的值，然后找与最小值相同的数字即可，这种需要从头到尾扫描数字两遍。
2.3 思路3
还有更快的方案，我只扫描所有数字一遍，把第一个数字当做最小，后面只把小于等于当前数字的记下来。这样我记下来的最后一个数字必然是最小的，然后从后往前看跟最小的数字相同的输出即可。
3. 实现
可以用数组实现，也可以用栈实现。因为输出是从后往前输出，正好符合栈后进先出的特点。代码如下：
/** * 获取最小的若干数字 * @author maoge * @date 2019-02-27 */ public class GetMinNum { /** * 入口 */ public static void main(String[] args) { int[] input = { 1, 2, 3, 1, 2, 1, 4, 5 }; System.out.println("====数组计算结果===="); getMinNumByArray(input); System.out.println(""); System.out.println("====栈计算结果===="); getMinNumByStack(input); System.out.println(""); } /** * 通过数组计算最小的几个数字 */ public static void getMinNumByArray(int[] input) { //定义用来输出的数组 int[] output = new int[input.length]; //输出数组当前操作位置 int location=0; output[location]=input[0]; for (int i = 1; i < input.length; i++) { if (input[i] <= output[location]) { location++; output[location]=input[i]; } i++; } //打印结果 for(int j=location;j>=0;j--) { //output[location]是最小值 if(output[location]==output[j]) { System.out.print(output[j]); } } } /** * 通过栈计算最小的几个数字 */ public static void getMinNumByStack(int[] input) { Stack<Integer> stack=new Stack<Integer>(); int min=input[0]; stack.push(min); //不大于最小的入栈 for (int i = 1; i < input.length; i++) { if(input[i]<=min) { stack.push(input[i]); } } //栈顶元素就是最小的元素 int peek=stack.peek(); while(stack.isEmpty()==false) { int num=stack.pop(); if(num==peek) { System.out.print(num); } } } }