搬家公司网站建设价格,wordpress实现语言,国企网站建设方案,搜索引擎友好的网站有哪些特点目录 问题描述
输入格式
输出格式
样例输入
样例输出
说明
评测数据规模
运行限制
原题链接
代码思路 问题描述
从小学开始#xff0c;小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期#xff0c;他遇到了一个非常有趣的问题小明就是一个非常喜欢数学的孩子。他喜欢用数学的方式解决各种问题。在他的高中时期他遇到了一个非常有趣的问题那就是给定一个长度为 n 的整数数组 nums 判断是否存在四个不同的下标 a,b,c,d 使得 a b c d 并且 nums[d] nums[c] nums[a] nums[b] 。
小明非常喜欢这个问题他决定用数学的方式来解决它。他首先想到了一个非常简单的方法那就是暴力枚举。他用四个循环来枚举所有可能的下标组合然后判断是否满足条件。但是这个方法非常耗时当 n 很大时计算量会非常大。
所以请求你给出一个快速智慧的解决办法。
输入格式
输入仅两行第一行包含一个整数 n 第二行包含 n 个整数其含义如上所述。
输出格式
输出仅一行包含一个字符串 YES 表示题目存在上面所描述的情况否则输出 NO 。
样例输入
4
3 4 2 1样例输出
YES说明
在样例中当 a,b,c,d 分别等于 0,1,2,3 满足 a b c d 并且使得 nums[d] nums[c] nums[a] nums[b]。
评测数据规模
对于 50% 的评测数据4≤n≤200−200≤nums[i]≤200 。
对于 100% 的评测数据4≤n≤5×105−109≤nums[i]≤109 。
运行限制
语言最大运行时间最大运行内存C1s512MC1s512MJava2s512MPython33s512MPyPy33s512MGo3s64MJavaScript3s64M
原题链接
四元组问题https://www.lanqiao.cn/problems/3416/learning/
代码思路
import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int nums[] new int[n];// smnum数组中每个值代表num[i]后面的最小的数.// 如:smnum[i]的值是num[i]后面的最小的数.int smnum[] new int[n];for (int i 0; i nums.length; i) {nums[i] scanner.nextInt();}smnum[n - 1] Integer.MAX_VALUE;// 因为题目中最大索引的值反而最小,所以要倒序.for (int i n - 1; i 1; i--) {smnum[i - 1] Math.min(smnum[i], nums[i]);}int a Integer.MIN_VALUE;// 用先进后出的栈也可以,用先进先出的队列也可以,,但用栈符合一般的逻辑习惯.// 上面的理由是这一步stack.peek() nums[i],提供的.StackInteger stack new StackInteger();for (int i 0; i nums.length; i) {// 题中要求是 nums[d] nums[c] nums[a] nums[b]// 与上面的一一对应 smnum[i] nums[i] a 栈里的元素if (a nums[i] nums[i] smnum[i]) {System.out.println(YES);return;}while (!stack.isEmpty() stack.peek() nums[i]) {// 因为a的值都是小于nums[i]的,所以栈里必有索引小于i且值大于a的.// pop()出栈,是为了提高效率.// 要是使用peek(),会超时.a Math.max(a, stack.pop());}stack.push(nums[i]);}// 没return,则输出NO.System.out.println(NO);}
}
