o(n)时间复杂度查找所有元素后面第一个比他大的数

小灰灰 2022-03-12 08:20 141阅读 0赞

# 说明 #

1.  **输入n个无序整数  
    输出 每个数之后第一个比他大的数,要求时间o(n)**  
    示例:  
    1,-1,2,3  
    输出:  
    2 2 3

解决思路:栈+栈底指针  
逻辑:(单调栈（单减栈，栈底元素代表最大元素）  
栈中存储元素位置索引  
int bottom=0;// 初始化栈底索引

# 分析: #

注意时间复杂度是o(n) 说明是只需要遍历一次,如果没这个限制,会自然而然想到两层循环遍历  
解决方式:栈+栈底指针  
**输入**:input\[\]  
输入第i个元素

1.  栈为空,i=入栈, bottom =i
2.  输入>栈底元素,那么栈中需要全部出栈(**始终保持栈底是最大元素**),执行1
3.  输入<=栈底元素,**不能直接入栈**,(因为可能栈顶元素比较小,那么新元素就是栈顶元素的后面的第一个比他大的元素)  
    3.1 输入<= 栈顶元素 ,直接入栈  
    3.2 输入> 栈顶元素,出栈,再入栈 (3.1,3.2 保证元素从栈底->栈顶保持非减顺序)(入栈前注意是否需要更新bottom指针)
4.  输入遍历完,栈中还剩余的元素则是不能找见之后比他大的元素

# java代码实现: #

将输出的序列放在了新的数组之中(也可以修改原数组)

/** * @author wangwei * @date 2019/3/7 14:03 * @classDescription 输入是一个无无序数组 * 输出:每个元素的之后一个第一个比自己大的元素 * 要求o(n) 的时间复杂度 */
    public class FindFirstBiggerAfterSelf { 
    
        public int [] solution(int[] input) { 
            if(null==input||0==input.length){ 
                return  null ;
            }
            Stack<Integer> stack = new Stack<>();
            int bottom = 0; // 初始化栈底指针
            int [] result=new int[input.length];// 记录搜索结果
    
            for (int i = 0; i < input.length; i++) { 
            //1. 栈空
                if (stack.isEmpty()) { 
                    bottom = i;
                    stack.push(i);
                    continue;
                }
                // 栈底是栈中最大元素
                // 假设栈中是 3 1
                // 输入是 2 3>2 入栈 ,但是2大于栈顶的1 ,也就是说 2 是1 后面第一个比他大的数
                // 这是应该将1弹出,2压入
                // 栈: 3 2
                // 输入 4 3<4 弹栈(清空栈) 4入栈
                // 栈: 4
               
                //2. 栈底元素大于等于输入
                if (input[bottom] >= input[i]) { 
                    // 需要判断栈顶是否也是比新元素大
                    // 栈顶较小,说明新元素是栈顶元素的后面的第一个比他大的元素
                    if (input[stack.peek()] < input[i]) { 
                        result[stack.pop()] = input[i];
                    }
                    // 这里保证了 栈中元素是: 栈底->栈顶 是由大到小的顺序
                    if (stack.isEmpty()) { 
                        bottom = i;// 更新栈底指针
                    }
                    stack.push(i);
                    continue;
                }
    
                //3. 输入元素大于栈底,那么全部弹栈
                while (!stack.isEmpty()) { 
                    result[stack.pop()] = input[i];
                  }
                bottom = i;
                stack.push(i);
    
            }
            // 4 .处理没找到之后的比他大的位置,此时索引应该还在栈中
            while (!stack.isEmpty()){ 
                result[stack.pop()]=Integer.MIN_VALUE;
            }
            return result;
    
    
        }
    
        public static void main(String[] args) { 
            int[] input = RandomUtil.randomInts(1, 20, 10);
            RandomUtil.printArray(input);
            System.out.println("------------------------");
           int [] result=new FindFirstBiggerAfterSelf().solution(input);
            RandomUtil.printArray(result);
        }
    }

测试:第一行是输入,分割线后是输出  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]: /images/20220312/61831a72d25349aeb5068117fcb90ea9.png