算法-查找单调元素

- 日理万妓 2023-10-01 20:25 11阅读 0赞

#### 文章目录 ####

*  1. 无序数组查找单调元素
 *  2. 解法

## 1. 无序数组查找单调元素 ##

在无序不重复的数组中寻找满足如下条件的元素：

> 1.  该值左边的数均小于它
> 2.  该值右边的数均大于它

例如给定数组 \{2,5,3,7,101,18\}，其中`元素7` 的左边元素都小于它，而右边的元素都大于它，故符合条件。如不存在符合条件的元素则返回 -1

## 2. 解法 ##

> 根据要求可将符合条件的元素作为锚点把数组分为两个部分，则这个元素不仅要是左半部分的最大值，还要是右半部分的最小值。 基于此，借助额外数组从右往左逆序记录目标数组截至每个下标的最小值，再从左往右顺序遍历计算数组最大值，如果该最大值小于额外数组对应下标位置后移一位的最小值，则符合要求

public int findAscElements(int[] nums) {
        
            if (null == nums || nums.length < 3) {
        
                return -1;
            }
            int len = nums.length;
            // 从右往左，记录每个下标及其之前所有数中的最小数
            int[] rightMin = new int[len];
            int rMin = nums[len - 1];
            for (int i = len - 1; i >= 0; --i) {
        
                if (nums[i] < rMin) {
        
                    rMin = nums[i];
                }
                rightMin[i] = rMin;
            }
    
            // 从左往右，寻找数组最大值，当其比右边下个下标上的最小数小时符合条件
            int lMax = nums[0];
            for (int i = 1; i < len - 1; ++i) {
        
                if (nums[i] > lMax) {
        
                    lMax = nums[i];
                    if (nums[i] < rightMin[i + 1]) {
        
                        return nums[i];
                    }
                }
            }
            return -1;
        }