浅谈求函数最宽尖峰的Java实现

小咪咪 2022-06-18 11:07 59阅读 0赞

函数最宽尖峰（函数最宽上升下降区间）：

一个数如果比它左右两边的都大，称为一个尖峰。

输入：第一行是数列长度，第二行是一个数字组成的数列，相邻的数字是严格单调递增或者严格单调递减的（相邻的数不相等）。

输出：数列中最宽的尖峰的左、右底部的坐标。若没有尖峰，则返回(-1,-1)。

思路：

设len为尖峰左、右底部之间的距离，low为左底部，high为右底部。result\[2\]纪录最宽的尖峰的左、右底部的坐标。

1）遍历数组1 ~ n - 1，判断nums\[i\]是否为尖峰；

2）找到尖峰后，向左循环找到尖峰左底部，纪录其坐标为low（向左单调减，也即nums\[low - 1\] < nums\[low\]，若不满足单调减，就到了左峰底）；同理，向右循环找到尖峰右底部high。求出此尖峰宽度distance = high - low；

3）如果len<distance，更新len的大小，并将low和high的坐标付给ret数组。

import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] nums = new int[n];
            sc.nextLine();
            String str = sc.nextLine();
            String[] strs = str.split(" ");
            for (int i = 0; i < n; i++) 
                nums[i] = Integer.parseInt(strs[i]);
    	    int result[] = new int[] {-1, -1};  
    	    int len = 0;  
    	    int low = 0, high = 0;  
    	    for (int i = 1; i < n - 1; ++i) {  
    	        if (nums[i] > nums[i-1] && nums[i] > nums[i + 1]) {  
    	            low = i - 1;  
    	            high = i + 1;  
    	            while (low >= 1) {  
    	                if (nums[low - 1] < nums[low])  
    	                    low --;  
    	                else   
    	                    break;  
    	            }  
    	            while (high < n - 1) {  
    	                if (nums[high] > nums[high + 1] )
    	                    high ++;  
    	                else   
    	                    break;  
    	            }  
    	            if (high - low > len) {  
    	                len = high - low;  
    	                result[0] = low;  
    	                result[1] = high;  
    	            }  
    	        }  
    	    }    
        	System.out.println(result[0] + " " + result[1]);
        }
    }