数组中每个元素左边大于或等于它的最近元素

17 Mar 2025 | 4 分钟阅读

给定一个整数数组，我们的目标是找到其中每个元素在左侧最近的、大于或等于该元素的值。本质上，我们需要构建一个新的数组，其中每个元素都对应于原始数组左侧最近的更大或相等的值。

例如，考虑数组：[5, 9, 3, 6, 8]。根据问题标准，新数组将是：[-1, -1, 5, 9, 9]。在这种情况下，对于第一个元素“5”，其左侧没有大于或等于它的元素，因此它保持“-1”。第二个元素“9”在其左侧没有大于或等于它的值，因此也是“-1”。第三个元素“3”在其左侧的最近大于或等于它的值是“5”。同样，第四个和第五个元素“6”和“8”在其左侧也有各自最近大于或等于它们的值。

注意：在查看解决方案之前，强烈建议您先思考一种方法。

暴力破解法

解决此问题的一种直接方法是使用暴力算法。对于数组中的每个元素，我们可以遍历其左侧并找到最近的大于或等于它的值。此方法涉及嵌套循环，时间复杂度为 O(n^2)，其中 'n' 是数组中的元素数量。虽然此方法在概念上很简单，但由于其效率低下，因此不适用于大型数组。

class Main {

    // Function to find the closest greater or equal value on the left side for each element
    public static int[] findClosestGreaterOrEqual(int[] array) {
        int n = array.length;  // Length of the input array
        int[] result = new int[n];  // Array to store the results
    
        // Loop through each element in the array
        for (int i = 0; i < n; i++) {
            int closestValue = -1;  // Initialize the closest value to -1
            
            // Loop through elements on the left side of the current element
            for (int j = i - 1; j >= 0; j--) {
                // Check if the current left-side element is greater than or equal to the current element
                if (array[j] >= array[i]) {
                    closestValue = array[j];  // Update the closest value
                    break;  // Break the loop as we found the required value
                }
            }
            
            result[i] = closestValue;  // Store the closest value for the current element
        }
    
        return result;  // Return the array containing closest values for each element
    }
    
    public static void main(String[] args) {
        int[] array = {5, 9, 3, 6, 8};  // Input array
        
        // Using the findClosestGreaterOrEqual function to get the result
        int[] result = findClosestGreaterOrEqual(array);
        
        // Print the result
        System.out.print("Resulting array: ");
        for (int value : result) {
            System.out.print(value + " ");
        }
    }
}

输出

Closest greater or same value on left side for every element in array

在此方法中，对于索引为 'i' 的每个元素，我们都从 'i-1' 遍历到 '0'，并找到最近的大于或等于它的值。此方法的时间复杂度为 O(n^2)，其中 'n' 是数组中的元素数量。

使用栈的优化方法

为了提高我们解决方案的效率，我们可以利用基于栈的方法。其思想是维护一个栈，该栈在从左到右遍历数组时，存储具有递减值的元素的索引。这确保了栈中的元素始终大于或等于当前元素。

当我们遇到每个新元素时，我们可以从栈中弹出元素，直到找到一个大于或等于当前元素的值，或者直到栈变空。栈顶元素（如果存在）的索引为我们提供了当前元素的左侧最近的大于或等于它的值。

此方法的时间复杂度为 O(n)，因为每个元素在栈中最多被推入和弹出一次。栈的大小从不超过元素数量，并且每个元素都恰好处理一次。

import java.util.*;

class Main {

    // Function to find the closest greater or equal value on the left side for each element
    public static int[] findClosestGreaterOrEqual(int[] array) {
        int n = array.length; // Get the length of the input array
        int[] result = new int[n]; // Array to store the closest values
        Stack<Integer> stack = new Stack<>(); // Create a stack to keep track of indices
    
        for (int i = 0; i < n; i++) { // Loop through each element in the array
            while (!stack.isEmpty() && array[stack.peek()] < array[i]) {
                // While the stack is not empty and the value at the current top of the stack
                // is less than the value of the current element
                stack.pop(); // Pop elements from the stack (remove smaller elements)
            }
    
            // After the while loop, the stack contains only indices of elements
            // with values greater than or equal to the current element
    
            // If the stack is empty, there is no element on the left side that is greater or equal,
            // so assign -1 as the closest value
            // Otherwise, assign the value of the element at the index from the top of the stack
            result[i] = stack.isEmpty() ? -1 : array[stack.peek()];
    
            stack.push(i); // Push the current index onto the stack
        }
    
        return result; // Return the array containing closest values for each element
    }

    public static void main(String[] args) {
        int[] array = {5, 9, 3, 6, 8}; // Input array
        
        // Using the findClosestGreaterOrEqual function to get the result
        int[] result = findClosestGreaterOrEqual(array);
        
        // Print the result
        System.out.print("Resulting array: ");
        for (int value : result) {
            System.out.print(value + " ");
        }
    }
}

输出

下一个主题从其对和数组构造数组

数组中每个元素左边大于或等于它的最近元素

注意：在查看解决方案之前，强烈建议您先思考一种方法。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数组中每个元素左边大于或等于它的最近元素

注意：在查看解决方案之前，强烈建议您先思考一种方法。

相关帖子

反向排序

打印 Q 查询的下一个更大数字

找到最大的三的倍数

数据结构中栈的入栈和出栈操作

稀疏集

分区为 K 个相等和的子集

二维二叉索引树或 Fenwick 树

从二维矩阵构造链表

N 元树的直径

检查一棵二叉树是否为另一棵二叉树的子树

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器